GATE CSE 2013 | Question: 33

Question

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

• A. 1 and 3 only
• B. 2 and 4 only
• C. 2 and 3 only
• D. 3 and 4 only

Answer 1

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$

Comments

Complement of a regular language is also a regular language.

---

@ayushsomani

sir,please give an example for the said statement

---

Option 2 can be checked to be true from the dfa given in q itself. No need to simplify.

For MIN-DFA

The language accepted by the string is: Contains at-least one $0$.Thus the reg exp: $1^*0(0+1)^*$

Hence Min-DFA:- 

- Pic from : @Praveen Saini Sir.

Thus option 3 and 4 are false straightaway.

Answer 2

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

Answer 3

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.

Answer 4

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