Aptitude Overflow
+8 votes
673 views

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 ⊂ L2
  3. L2 ⊂ L1
  4. None of the above
asked in Theory of Computation by (19.4k points)   | 673 views
One of the zero edge has the arch missed
Thanks. It is Z-> Y for 0.

5 Answers

+13 votes
Best answer
In Qs. Z -> Y (0 edge)

L1 can have 00 string while L2 can't. L2 can have 01 while L1 can't

So we can conclude neither they are same set not proper subset of each other.

Hence Ans. D.
answered by (3.4k points)  
selected by
y to z arrow  value seem misprinting kindly check it plz

why L1 can not accept "01" . question seem totally misprinted.

Didn't get this solution.

L1 and L2 both can have 0 as string which they both can accept. Moreover L1 and L2 can also have 000 as string.
+2 votes
Misprints : Edge Y -> Z ( 0 edge )
                      Edge Z -> 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).
answered by (695 points)  
+1 vote

if we take Y$\rightarrow$Z for transition

and Z$\rightarrow$Y for 0 transition,

then L1 accepts strings ending with '0' and L2 accpets strings ending with '1'

and both sets are totally disjoint. 

so answer is D.

 

answered by (2.7k points)  
L2 also accepts strings ending with '0'. The criteria is 00 and 01.

L1 accepts strings ending with 00. And L2 with 01.

So, they are disjoint.
If we take  Y to Z =0 and  Z to Y =1

then L1=L2
0 votes

for  string 00 L1 can accept but not by L2 and for string 011  L2 can accept but not by L1  so  disjointness b/w them so D will be answer and dont bother the direction b/w Y TO Z for input 0

answered by (3.9k points)  
0 votes

A generic approach to solve such questions would be to come up with the corresponding regular languages and compare the two. 

Solution 1:

Ardens theorem could be used to achieve the objective. Moreover, some conclusions could be drawn without even deriving the languages completely, solely from the intermediary equations.

Constructing equations for every state -: X = Z0 +X1, Y = X0 +Y0 +Z0 && Z = X0 + Y1 + Z1.

Clearly, regular languages L1 and L2 couldn’t be same. Now, to check which of the other three options are correct, we need to find : 1) a string which is accepted by L1 but not by L2. 2) a string which is accepted by L2 but not by L1. If there exists string 1) but not 2) then L2 ⊂ L1 and likewise. Trying our hands at the given DFA, 1) string 00 is accepted by L1 but not by L2 and 2) string 01 is accepted by L2 but not by L1. Hence, neither of the two languages our subset of the other.

Solution 2. 

L1 can have 00 string while L2 can't. L2 can have 01 while L1 can't None of them can be either equal or proper subset of each other. 

So Ans. D.

answered by (3.4k points)  

Related questions

2,455 questions
849 answers
346 comments
15,474 users