3.2k views

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 | 3.2k views

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
+4

@Praveen Saini   Sir, in

Sir, which property is this? How did you write this?

+12
$(0+1)^*\{\epsilon ,0,00,......\}\{\epsilon ,1,11,......\}$

$(0+1)^*\{\epsilon ,0,00,......1,11.....01,011,......001,0011,....\}$

$(0+1)^*+(0+1)^*0+(0+1)^*00+......+(0+1)^*1+(0+1)^*11+.....$
0
@Praveen Saini Sir, How the first statement under Note is True?
0
@anchit as in comment as above.
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

1
2