edited by
1 flag 12,409 views
56 votes
56 votes

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?

  1. $L_1 = L_2$
  2. $L_1 \subset L_2$
  3. $L_1 \cap  L_{2}^{C} = \varnothing $
  4. $L_1 \cup L_2 \neq  L_1$
  • 🚩 Edit necessary | 👮 simeonsg | 💬 “For this question, both A,C are correct. So in question it should be mentioned which is/are of the following are TRUE?”
edited by
1 flag

6 Answers

Best answer
57 votes
57 votes

$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.

edited by
4 votes
4 votes
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.
2 votes
2 votes

Answer: A.

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

0 votes
0 votes

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)

Answer:

Related questions

30 votes
30 votes
5 answers
2
Ishrat Jahan asked Oct 27, 2014
10,694 views
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recogniz­ing the same language. Which of the following in NECESSARILY true?$m \leq 2^n$$...
44 votes
44 votes
7 answers
4
Ishrat Jahan asked Oct 28, 2014
14,807 views
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...