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.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,779 questions

46,781 answers

140,753 comments

58,681 users