Consider the DFA given below.
Which of the following are FALSE?
- Complement of L (A) is context–free.
- $ L(A) = L((11^0+0)(0 + 1)^*0^*1^) $
- For the language accepted by A, A is the minimal DFA.
- A accepts all strings over {0, 1} of length at least 2.
-
1 and 3 only
-
2 and 4 only
-
2 and 3 only
-
3 and 4 only
D
Correct answer
Explanation
(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 00 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’ (atleast length one).