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

language L1L2 has a DFA where start of M1 is start, final states of M2 are final states. When we reach to  final of M1, it is connect with start of M2.

when we remove ^-transition from it we get the DFA given in part A.

---

For part b, epsilon transitions from C to A and D to A are required.

---

Am I wrong?

---

what to do for part B? @praveen saini

---

by adding null transition in answer selected from state D to state AC

---

Hi @Arjun Sir  can you explain bit more on part b?

I am not getting what (L1.L2)∗ contains? and how to draw diagram for it.

---

How the given finite automa satisfy part (b) i.e. ${(L1•L2)^*}$

---

For Part (b), we need to add a null transition from state D to A in the diagram of part (a).

Since (L1.L2)* contains at least a single b for L2 i.e. {b,ab,ba,bb, abb etc.}, so we don't put a transition from C to A.

---

for second part (L1.L2)*

---

U cannnot put Null transition from A to D instead null transition will be from D to A and may be C to A also  but definetly not from A to D

---

"definitely" is a strong word to use, so use it not very frequently :)
There is a transition from A to D because (L1.L2)* contains epsilon also, in fact kleene closure of any language L contains epsilon.
And there is a transition from D to A because of L*, there can be any number of transitions of L

---

Actually we can say that we should put null transition at all the three places because we don't what actually we have to read from A because there are multiple final states

---

what is the need of A-> D when previously FA accepting epsilon through A->C?

---

@Spider1896 actually we convert multiple final states into one final state using epsilon transition, and to compute L* for a language L, we use two another epsilon transitions one from start state to final state and second from final state to start state.

@Shubhgupta when build DFA for two languages L1 and L2 such as L1.L2 then we make all the final states into non-final of first DFA which accepts L1, and connect epsilon transitions from each final state in DFA1 to initial state of DFA2.

---

@chauhansunil20th , but my question is when you drew FA for second part then language already accepting epsilon through A->C then what is the need for one extra transition of A-> D? Because other epsilon this edge is not helping in any other input.

---

I think there are 4 epsilon- transition of the (L1.L2)*.

AC & AD are 2 way. so total 4

according to protocol what chauhansunil20th said is correct.

here is part b of this question we need to add 3 more e-transition.

C to A, A to D, D to A

---

@MRINMOY_HALDER Why A to D null transition is required ?

---

If u talking about basic protocol to make any DFA into it's kleen closure, then yes there should be null transition from start state to final state, otherwise you can make +ve-closure, but not kleen-closure.

draw a nfa of 'a' & make it a*, you will understand.

but here you can argue that without null transition from A to D is not a problem,because there is a null transition from A to C.

---

@Arjun, Hi sir, i had a doubt, L2 can also accept epsilon as C is a final state so (L1*L2) = L1 when L2 is epsilon, so the resulting automata should accept only L1 also then why did you make A as a non-final state.

---

• M1 = { |w|%2=0  (even length string)},
• M2 = {a^n b^m ;n,m>=0}

So, both languages contain epsilon,hence L1.L2 will also contain epsilon. I think, in given solution diagram,state-A should also be the final state.

Please varify it @arjun sir and correct me.

---

 

Source: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_06.pdf (Page-5)

For any integer n ≥ 2, let A be an n-state NFA that accepts a star-free language. Then n + 1 states are sufficient for an NFA to accept the Kleene star of the language of A. 

Let L a language accepted by an n-state DFA. Then the minimal DFA for the language L* has at most 3/4·(2^n) states.

Hence the complexity will be linear in case of NFAs, while exponential in case of DFAs. 

Source: https://core.ac.uk/download/pdf/82169573.pdf (Page-7) 

               http://ceur-ws.org/Vol-1003/94.pdf (Page-3)

 

---

by adding null transition in answer selected from state D to state AC

@Praveen Saini Sir I don’t think we need to make D--∈-->C, as it’s concatenation (L1.L2)* and not (L1∪L2)*. So the ∈ transitions will be from C->A and D->A i.e. Final states to Initial state. Correct me if I’m wrong.

---

@Praveen Saini can someone state about the part B

---

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.