The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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.

asked in Theory of Computation by Boss (17.4k points) | 101 views

1 Answer

0 votes

[ 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.

answered by Boss (17.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,262 questions
49,758 answers
65,849 users