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

So is the answer for this question only A or A,C?

---

what's the actual version? some versions have is/are True , one of the following true , option C as L1 ∩ L2

---

L(1) = (0+10)*11(1+0)*

L(2) = (0+1)*11(1+0)*

Option A,C are correct

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 .

---

I got the answer by converting the M2 into minmized DFA but how did you say that $(0 + 10)^*$ and $(1+0)^*$ i didn't get it?

---

isnt answer : A,C,D implying that a set is subset of itself ?
so L1 is a subset of L2 and vice versa

---

doubt arises; only because, we think that as only the prefix of each regex is different are rest part are same

so we start comparing only (0+10)* part of regex of L1 and (0+1)* part of regex of L2, Individually

and individually these parts of original regex are indeed proper subset i.e, (0+10)*  is proper subset of (0+1)* : so we start thinking option B is correct 

you can conclude L1 = L2 iff, you compare the whole regex; much easier way is to notice that m2 is nfa and making dfa for m2 

mfa(m1) = mfa(m2) so L1 = L2

---

@RahulVerma3

(0+10)* and (1+0)* are not at all equivalent.

They only become equivalent in the context of the entire expression.

In L1, if there is any 0* or any (10)* or any mixture of 0 and 10, it can easily be handled by (0 + 10)*, but if there is a 11, we can consider that to be handled by the compulsary substring 11 and the remaining portion of the string can be handled by the (a + b)* which comes after it.
 

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.

Comments

Can you please share the solution if possible?

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.

---

bro first convert in to dfa then apply complement concept !

Answer 4

For those who have not idea how to convert NFA to DFA

Comments

Isn't your NFA to DFA conversion wrong(Second Diagram)?

Coz q0q1(1)->q0q1

q0q1(0)->q0

But you missed those transitions.

 

In the final diagram,you forgot to put loop on q2.

Answer 5

M2 is NFA. If M2 is converted to DFA, it will become exactly same as M1. Hence L1 and L2 are same set of languages. Thus option A and C are correct

Answer 6

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)