Question

Consider the DFA 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

Correct option is (D) 3 and 4 only

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L(A) = (11*0+0) (0+1)* 0* 1* = 1*0 (0+1)*

Language has all strings where each string contains '0'.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains '0'. (at least length one)