Question 33

Let us inspect the given DFA $A$:

• State 0 is the start state.
• State 1 is an intermediate non-accepting state.
• State 2 is the accepting state.

Transitions:

• From state 0: on 0 $\rightarrow$ state 2; on 1 $\rightarrow$ state 1.
• From state 1: on 0 $\rightarrow$ state 2; on 1 $\rightarrow$ state 1 (self-loop).
• From state 2: on 0 $\rightarrow$ state 2; on 1 $\rightarrow$ state 2 (trap/accepting self-loop).

Notice that if any string contains at least one '0':

• If it starts with 0, it immediately reaches state 2 (accepting).
• If it starts with one or more 1s, it stays in state 1 until the first 0 appears, which moves it to state 2 (accepting).
• Once in state 2, all further symbols keep it in state 2.

Thus, $L(A)$ is the set of all strings over $\{0, 1\}$ containing at least one '0':

Now test each statement:

1. Complement of $L(A)$ is context-free: The complement of $L(A)$ is the set of strings with no zeros, which is $1^*$. Since $1^*$ is regular, it is also context-free. Thus, statement 1 is TRUE.
2. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$: Notice $(11^*0 + 0) = (1^+ 0 + 0) = 1^* 0$. The expression $(0 + 1)^* 0^* 1^*$ simplifies to $(0+1)^*$. Thus, $(11^*0+0)(0+1)^*0^*1^* = 1^* 0 (0+1)^*$, which matches exactly all strings containing at least one '0'. Thus, statement 2 is TRUE.
3. For the language accepted by A, A is the minimal DFA:
   Examine states 0 and 1:
   • $\delta(0, 0) = 2$ and $\delta(1, 0) = 2$.
   • $\delta(0, 1) = 1$ and $\delta(1, 1) = 1$.
     Both states transition to the exact same state for every input symbol, and neither is an accepting state. Therefore, states 0 and 1 are equivalent and can be merged into a single start state. The minimal DFA for $L(A)$ has only 2 states. Hence, A is not minimal. Statement 3 is FALSE.
4. A accepts all strings over $\{0, 1\}$ of length at least 2:
   Consider the string "11". Its length is 2, but on input "11", the automaton transitions $0 \xrightarrow{1} 1 \xrightarrow{1} 1$. State 1 is not accepting, so "11" is rejected. Thus, statement 4 is FALSE.

Statements 3 and 4 are FALSE, which corresponds to option (D).