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

This question was previously asked in

GATE CS 2013 Official Paper

Option 4 : 3 and 4 only

IBPS SO IT Officer Mains: Full Mock Test

4812

60 Questions
60 Marks
45 Mins

The correct answer is **option 4.**

__Key Points__

1. The complement of L(A) is context-free.

** True**, According to closure property complement regular language is regular. And every regular language is context-free.

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

**True**, Above DFA accepts the regular equation and generate the strings like {0,00,01,10,000,001,010,011,100,101,110,..}

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

** False**, The given DFA can be minimized to two states and the minimal DFA is,

4. A accepts all strings over {0, 1} of length at least 2.

** False**, DFA accepts the string of length 1 and accepted strings are {0,00,01,10,000,001,010,011,100,101,110,..}

** Hence the correct answer is*** 3 and 4 only.*

__Additional Information__

* *