Project ForgeConsider a DFA A with start state q0 --1--> q1, q0 --0--> q2 (accepting), q1 --1--> q1 (self-loop), q1 --0--> q2, and q2 --0,1--> q2 (accepting, self-loop). 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.
- A1 and 3 only
- B2 and 4 only
- C2 and 3 only
- 3 and 4 only
Explanation
L(A) = {strings containing at least one 0}. Its complement is 1* (regular, hence also context-free) — statement 1 TRUE. The given regex (11*0+0)(0+1)*0*1* also generates exactly 'contains at least one 0' — statement 2 TRUE. However, q0 and q1 are equivalent states (both are 'no 0 seen yet' with identical future behaviour), so A is NOT minimal — statement 3 FALSE. And A does not accept all length-≥2 strings, e.g. '11' is rejected — statement 4 FALSE. So statements 3 and 4 are the false ones.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.