GATE CSE 1996 | Question: 12

Question

Given below are the transition diagrams for two finite state machines $M_1$ and $M_2$ recognizing languages $L_1$ and $L_2$ respectively.

• A. Display the transition diagram for a machine that recognizes $L_1.L_2$, obtained from transition diagrams for $M_1$ and $M_2$ by adding only $\varepsilon$ transitions and no new states.

• B. Modify the transition diagram obtained in part (a) obtain a transition diagram for a machine that recognizes $(L_1.L_2)^*$ by adding only $\varepsilon$ transitions and no new states.

  (Final states are enclosed in double circles).

Comments

@yuyutsu 
That’s correct. 

---

@yuyutsu one small mistake in b part is for state C there must be one self loop for alphabet a.

---

@yuyutsu
in part A in your solution state A wouldn’t be a final state.

Answer 1

We can combine the final state of $M_1$ with the start state of $M_2$ as follows recognizing $L_1L_2$. But before we combine $M_1$ and $M_2$ remove the final state of $M_1$ as the new machine can accept $L_1$ also while it should accept only $L_1.L2$.

~Pic by Praveeen Saini

Comments

the regular expression for 

  L2 = { a^n.b.b^n  | n >=0 }

  therefore, smallest possible string that L2 can generate is ‘”b “(not epsilon)

and, it is epsilon in case of L1.

As,  (epsion).(b) = b.

therefore ,, initial state cannot be an accepting state

            

---

M2 is a^n b^n ,n>=0;so epsilon can be accepted

---

Language accepted by M1 is L1=(00+01+10+11)* and M2 is L2= a*b*.

So L1.L2=(00+01+10+11)* a*b*

In the both the DFA’s of Ques(a) and (b) state A can be final state as there is a null transition from A to C. So making A as final or non final doesn’t change the language accepted by FA.