edited by
16,175 views
49 votes
49 votes

Consider the DFA $A$ given below.

 

Which of the following are FALSE?

  1. Complement of $L(A)$ is context-free.
  2. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*) $
  3. For the language accepted by $A, A$ is the minimal DFA.
  4. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$.
  1. 1 and 3 only
  2. 2 and 4 only
  3. 2 and 3 only
  4. 3 and 4 only
edited by

4 Answers

Best answer
92 votes
92 votes
  1. Complement of $L(A)$ (regular language) is regular and hence also Context Free. True 
  2. Regular expression is $(11^*0 +0)(0+1)^*$  True 
  3. Minimized DFA is:     

    Both non-final states are equivalents and can be minimized
    So, $3$ is False 
  4. From $3$, shortest length string reached from $q0$ to $q1$ (final) is $0$, so $4$ is False 

Note :

  1. $(0+1)^*0^*1^* = (0+1)^* + \text{something} =(0+1)^*$
  2.  $(11^*0+0)(0+1)^* = (11^*+  \epsilon)0(0+1)^* =1^*0(0+1)^*$ look at Minimized DFA at $3$.

Correct Answer: $D$

edited by
6 votes
6 votes
i just used option elimination method in this question.
for example lets see point 4. we can clearly see that it is false beacuse smallest string can be 0.
now clearly option A and C will be eliminated because it doesn't contain point 4.

now we can easily check using transition table of dfa that the given dfa is not minimal.
so answer will be D

P.S These will work faster as in  point 2  we may have to use ardent method i.e state elimination method for finding regular expression and that will be time consuming
0 votes
0 votes

L(A) is regular and its complement is also regular (by closure property) and every regular is CFL also. So Complement of LA is context-free.
The regular expression corresponding to the given FA is

Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the non-final states are equivalent and can be merged and the min DFA will have two states which is given below:

Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.

–5 votes
–5 votes
4: a single 0 is also accepted thats why 4 is false 1:the complement is also a reg lang 2 and 3 are correct
Answer:

Related questions

44 votes
44 votes
2 answers
1