GATE CSE 2023 | Question: 53

Question

Consider the language $L$ over the alphabet $\{0,1\}$, given below:
\[
L=\left\{w \in\{0,1\}^{*} \mid w \text { does not contain three or more consecutive } 1 \text { 's }\right\} .
\]
The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Answer 1

the given problem is simply a complement of MDFA having 3 consecutive 1’s over the input $(0,1).$ We can take complement by simply changing the non-final state to the final state and vice-versa.

The MDFA not containing 3 or more consecutive 1’s will require $4$ state out of which $3$ are final and $1$ is dead states.

it will accept strings like $(\epsilon,0,1,00,01,10,11,000,001,010,011,100,101,110...\infty)$

it will reject strings like $(111,1110,11101,11111,111000,1110101,111001...\infty)$ 

the correct MDFA is as follows:

The correct answer is $4$

Answer 2

Detailed Solution: Number of States in the Minimal DFA

$\color{\red}{\text{All Theory of Computation Questions:}}$

Question 1: PDA Push Down Automata Question

Question 2: Context Free Grammar But Language Regular

Question 4: Intersection Closure Property based Question

Question 5: DFA to Regular Expression question: 1(0+11)*

Answer 3

the given problem is simply a complement of MDFA having 3 consecutive 1’s over the input $(0,1).$

we can take complement by simply changing the non-final state to the final state and vice-versa.

The MDFA not containing 3 or more consecutive 1’s will require $4$ state out of which $3$ are final and $1$ is dead states.

it will accept strings like $(\epsilon,0,1,00,01,10,11,000,001,010,011,100,101,110...\infty)$

it will reject strings like $(111,1110,11101,11111,111000,1110101,111001...\infty)$ 

the correct MDFA is as follows:

Correct answer is $4$

Answer 4

Caption