Question

Consider the DFA A is given below:

Which of the following are False?

1. Complement of L(A) is context-free.

2. L(A) = $L\left(\right({11}^{\ast }0+0\left)\right(0+1{)}^{\ast }{0}^{\ast }{1}^{\ast })$

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.

Answer 1

1. A is a NFA. So L(A) is regular. Complement of L(A) is also regular, since regular languages are closed under complement. So, L(A) is context-free is true.

2. $L\left(A\right)=L\left(\right({11}^{\ast }0+0\left)\right(0+1{)}^{\ast }{0}^{\ast }{1}^{\ast })$ : true because the r.e. for the language accepted by above automata is (11*0+ 0) (0+1)*.

3. For the language accepted by A, A is the minimal DFA: false

Writing the r.e. for the language accepted by the given DFA and simplifying. we get,

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

= (11* + $\in$) 0(0+1)* = 1*0(0+1)*

The minimal DFA for the above language is

4. Machine A accepts all the string over {0, 1} of length at least 2: False

Above DFA accepts string "0" whose length is less than 2.