in Theory of Computation edited by
12,700 views
47 votes
47 votes

Consider the non-deterministic finite automaton (NFA) shown in the figure.

State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ as the only accepting state be $L1$. Similarly, let the language accepted by the NFA with $Z$ as the only accepting state be $L2$. Which of the following statements about $L1$ and $L2$ is TRUE?

  1. $L1 = L2$
  2. $L1 \subset L2$
  3. $L2 \subset L1$
  4. None of the above
in Theory of Computation edited by
12.7k views

4 Comments

edited by
L2 accepts 101010 but L1 doesn't then how L1=L2.

PS : L1 also accepts.
0
0

Both accepts it for L2 repeat state XZZXXZ

 for L1  XZZXXY

@ASNR1010

0
0
edited by

L1 also accepts 101010.

0
0

4 Answers

76 votes
76 votes
Best answer

Misprints : Edge $Y \rightarrow Z$ ( $0$ edge )
                   Edge $Z \rightarrow Y$ ( $1$ edge )

Answer: A.

Explanation:

Writing $Y$ and $Z$ in terms of incoming arrows (Arden's method) :

$Y = X0 + Y0 + Z1$

$Z = X0 + Z1 + Y0$

Hence $Y=Z$. So, option (A).

edited by

4 Comments

please elaborate....what are you asking?
0
0
I want to know how to write state diagram into this kind of expressions ...

 

Y=X0+Y0+Z1
Z=X0+Z1+Y0

Any resource to learn that properly...
0
0
Study ardens theorem etc
0
0
20 votes
20 votes
convert this nfa to dfa , you will get the dfa with same final states  for both the cases , so option A is correct

4 Comments

Time Consuming ...
0
0
edited by

@itsvkp1 yes the two DFA's will be exactly same except the final states, for L1 DFA the no of final states=4 whereas for L2 it is 1 only.. then how are two languages equal?

Please explain

1
1
Wrong DFA
0
0
puja mishra, it is not at all time consuming, u just need to be thorough
0
0
7 votes
7 votes

converting NFA to DFA,

both DFAs are same so,L1=L2

2 Comments

@Abhishek Tank how do you know after converting nfa to dfa that state yz represents y only and state xyz represents state z of nfa ???

0
0
Helpful👍
0
0
1 vote
1 vote

Nice Explanation GFg

P.s Different ans due to  different assumption.

edited by

2 Comments

Same answer on GFG now
0
0
GFG solution about interium edges
Can we apply only in NFA ?
0
0
Answer:

Related questions