CMI2017-B-1

Question

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 \in Σ^*$  and erases all occurrences of the pattern $ab$ from $w$. Formally, it can be defined as follows:

Erase$_{ab}$(w):=$\left\{\begin{matrix} w &\text{if $w$ does not contain the pattern $ab$} \\ Erase_{ab}(w_{1})\:Erase_{ab}(w_{2}) & \text{if } w=w_1\:ab\:w_2 \text{ for some} w_1,w_2\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:$

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

Show that $Erase_{ab}(L_{even}$) is a regular language.

Answer 1

[ Official answer by CMI ]

(a) L_even 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) Erase_ab(L_even) 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 L_ab 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 L_ab is regular, so is its complement L$\bar{ab}$, the language of all strings without ab. Erase_ab(L_even) is the intersection of L$\bar{ab}$ with L_even.

Answer 2