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

@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)