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

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)