100 views

Let Σ = {a, b, c}. Let Leven be the set of all even length strings in Σ*

(a) Construct a deterministic finite state automaton for L$_{EVEN}$.

(b) We consider an operation Erase$_{ab}$ that takes as input a string w ∈ Σ*  and erases all occurrences of the pattern ab from w. Formally, it can be defined as follows:

Erase$_{ab}$(w):=$\left\{\begin{matrix} w &if\:w\:does\:not\:contain\:the\:pattern\:ab \\ Erease_{ab}(w_{1})\:Erease_{ab}(w_{2}) & if\: w=w1\:ab\:w2\:for\:some\:w1,w2\in \Sigma * \end{matrix}\right.$

For instance, Erase$_{ab}$(cacb) = cacb, Erase$_{ab}$(cabcbab) = ccb and Erase$_{ab}$(ab) = $\epsilon$.

For a language L, we define $Erase_{ab}(L)$ to be the set of strings obtained by applying the $Erase_{ab}$ operation to each string in L:

Erease$_{ab}$(L):= {  Erease$_{ab}$(w) | w$\in$ L}

Show that Erase$_{ab}$(L$_{even}$) is a regular language.

[ Official answer by CMI ]

(a) Leven can be recognized by an automaton with two states {q0, q1}, where q0 is both an initial and final state. On input letters a and b, the automaton switches from q0 and q1 and vice versa. An odd length input will take the automaton to q1 and an even length input will take the automaton to q0.

(b) Eraseab(Leven) is the set of all even length strings which do not contain ab. It is easy to construct a nondeterministic automaton with three states {q0, q1, q2} for the language Lab consisting of all strings containing ab. Here, q0 is the initial state and q2 is the final state. There is a self loop on {a, b} at both q0 and q2 and there are transitions q0 $\overset{a}{\rightarrow}$ q1 and  q1 b$\overset{b}{\rightarrow}$ q2. Since Lab is regular, so is its complement L$\bar{ab}$, the language of all strings without ab. Eraseab(Leven) is the intersection of L$\bar{ab}$ with Leven.