GATE IT 2008 | Question: 36

Question

Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.

$M_1$

$M_2$

 

Which one of the following is TRUE?

• A. $L_1 = L_2$
• B. $L_1 \subset L_2$
• C. $L_1 \cap  L_{2}^{C} = \varnothing $
• D. $L_1 \cup L_2 \neq  L_1$

Comments

both machine are containing 11 as substring so i said equal  or other way to test convert nfa to dfa and then  minimize the dfa bcz dfa can have more state in comparision to nfa. after minimizing you got both equal  

---

A → C

B → D

Answer 1

$L_1: (0 + 10)^*11(0 + 1)^* $

$L_2: (0 + 1)^*11(0 + 1)^*$ 

It is quite clear that $L_1 = L_2$.

As both languages $L_1$ and $L_2$ are equal So Complement of Language $L_2$ will be the complement of Language $L_1$ also. For a given language $L, L \cap L^{c} = \emptyset.$

Hence, both options (A) and (C) are correct.

Comments

Even though everything is correct , L1= L2 , as M1 is DFA of NFA M2

but I am getting L1= (0+10)*11(0+1)* using Arden's theorem.

How did you calculate L1 ?

---

Hi Pravin, that was a mistake. I have edited it.

---

isn't it l1 subset l2?

---

L1=L2 , L1 is subset of L2 and L2 is subset of L1.

---

Sir, how did you find this?

---

first convert m2 to dfa , which has 4 staes & when minimizing that dfa you will get m1. therefore l1=l2;

---

thks

---

IF L1=L2 then option c L₁ ∩ L₂' = ∅ is also correct..so both A and C correct

---

Please anybody provide the solution of L1 by Arden's theorem Thanks

---

@Praveen Saini @kumar_sanjay Sir, if R.E are 

L1: (0 + 10)*11(0 + 1)* L2: (0 + 1)*11(0 + 1)*

then people got L1=L2,  but from L1 we can generate 1011, but how to generate string 1011 from L2? 

Then how can L1=L2 ?!

---

$\underbrace{(0+1)^*}_{10}\underbrace{11}_{11}\underbrace{(0+1)^*}_{\epsilon}$

---

@ Praveen Saini  You're the best, Sir!

---

Why can't the first DFA be interpreted as " if the string contains atleast 2 1's then accept" ?

Interpreting like this will make option c as correct answer ie atleast 2 1's intersect complement(exactly 2 1's) is NULL

---

1) First DFA is not for at least 2 1's

2) atleast 2 1's intersect complement(exactly 2 1's) is not NULL

---

yeah got it . Misinterpreted it earlier .

---

Hi @Praveen Saini ji,

L1=L2 , L1 is subset of L2 and L2 is subset of L1.

Correct. But how can we prove above mentioned statement ?

---

you can find the minimized DFA for M1 and M2. if you get the same then L1 = L2

---

Hi @Praveen Saini ji Thank You.

you can find the minimized DFA for M1 and M2. if you get the same then L1 = L2

Can not we obtain two different minimized DFA for same L ?

If Yes the $M_{1}$ XOR $M_{2}$ == $\phi$ may help. 

One more thing is there any other more faster way to do this. 

---

No, if L1 = L2, then Minimized DFA will be same.

if you do not want to do the minimization of DFA's.

Then you can find cross product of two DFA, if we always get final states together in cross product, then L1= L2

---

@praveen sir rather than taking arbitrary length string ... if we take fixed Length 3 bit string and its all possibilities  ... and then we compare the options ... is it a correct approach ??

---

@praveen sir how to find cross product and check it can u plzz explain ??

---

Can someone provide steps by applying Arden's theorem in this question?

---

Converting the NFA to DFA, then minimizing it.. is a cumbersome process. Isn't there any shortcut?  Please help..

---

There is no shortcut for nfa to dfa conversion But if you somehow get regular expression or language generated by nfa then you can draw corresponding dfa..

---

@Praveen Saini Sir, I am having difficulty understanding how Regular expressions for L1 and L2 are equivalent. Particularly the part (0+10)* and (0+1)*. My actual doubt is , suppose  R.E1= (0+10)* and R.E2 = (0+1)* , are they equal in this case too?
No, right?

---

yes i am too confused in this part

so at first i thought that L1 is subset of L2

please help in this.

---

because how can we get 01111 in (0+10)*  and it is possible in (0+1)*

---

@gaganjot My thoughts exactly. Shouldn't the right answer be B in this case? Since (0+1)* contains (0+10)* as a subset while looking at the regular expression alone?

---

@gaganjot (0+1)* and (0+10)* are not the same. If you think about it, (0+10)* does not produce strings ending in 1 whereas (0+1)* can. But, When you see the entire regular express as a whole both gives out the same language.

---

why are we focussing on the regular expression for the given FAs, I think it is easier to interpret what they are doing. In this case both are accepting any string that contain 11 as a substring. Correct me if  I’m wrong

---

Ans A is wrong, Because  L1 generate 1011 string but L2 can’t generate 1011.

---

@Ajitgate21 M2 also can generate L2 (1011). Follow these states for L2 : $AABC$ Recheck once more.

---

@Abhrajyoti00 Thank you for reply

---

wheather (0+1)* = (0+10)* ?

because if they both are equal then only you can say that both L1 and L2 are equal .

Answer 2

Both the machines looks to be accepting the same language . M1 is a DFA and M2 is a NFA . So simply for verification convert NFA ( M2 ) to DFA and perform state reduction operation on DFA to get minimal DFA . We can see that the result is machine ( M1 ) . For those who don't wish to play much with regular expressions can use this technique.

Answer 3

Answer: A.

option c) cannot be right as complement concept is only applicable for DFA.

Comments

@swagat

We are not applying Complement on NFA. We are applying complement on the Language (i.e. $L_{2}$) accepted by given NFA. Therefore, A and C are Correct.

Answer 4

In this L1 = (0+10)* 11(0+1)*
L2 = (0=1)* 11(0+1)*
Both L1 and L2 are equal.
Option A is correct.
→ L1 ∩ L2‘ = L1 ∩ L1‘ = ∅ (option C also correct)