The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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.

0 votes

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,161 questions

43,619 answers

124,003 comments

42,880 users