GATE CS 2013 Q33 — Regular Expressions and Finite Automata

Let us analyze each statement based on the language of the DFA $A$:

• Statement 1 is TRUE: Since $A$ is a DFA, the language $L(A)$ is regular. Regular languages are closed under complementation, and every regular language is also context-free.
• Statement 2 is TRUE: The regular expression $(11^*0 + 0)(0+1)^*0^*1^*$ simplifies to $1^*0(0+1)^*$, which represents the set of all strings over $\{0, 1\}$ containing at least one $0$. The given DFA $A$ accepts exactly this language.
• Statement 3 is FALSE: The minimal DFA for the language "at least one $0$" requires only $2$ states (a start state that loops on $1$ and goes to an accepting state on $0$, which then loops on both $0$ and $1$). The given DFA $A$ has $3$ states, meaning it is not minimal.
• Statement 4 is FALSE: The string $11$ has a length of $2$ but contains no $0$, so it is not accepted by $A$. Thus, $A$ does not accept all strings of length at least $2$.

Since statements 3 and 4 are FALSE, the correct option is D.