GATE CS 2023 Q53 — Regular Expressions and Finite Automata

The language $L$ consists of all strings over $\{0,1\}$ that do not contain the substring $111$. We can construct the minimal DFA by tracking the number of consecutive $1$s seen at the end of the input string.

Let the states represent the following tracking information:

• $q_0$ (Start, Accepting): No consecutive $1$s at the end (the last character read was $0$, or the string is empty).
• $q_1$ (Accepting): Exactly one consecutive $1$ at the end.
• $q_2$ (Accepting): Exactly two consecutive $1$s at the end.
• $q_3$ (Non-accepting, Trap): Three or more consecutive $1$s have been seen (the substring $111$ has occurred).

The transitions are defined as follows:

• From $q_0$: on $0 \to q_0$, on $1 \to q_1$
• From $q_1$: on $0 \to q_0$, on $1 \to q_2$
• From $q_2$: on $0 \to q_0$, on $1 \to q_3$
• From $q_3$: on $0, 1 \to q_3$

To verify minimality, we check if any states can be merged:

• $q_3$ is non-accepting, while $q_0, q_1, q_2$ are accepting, so $q_3$ cannot be merged with any other state.
• From $q_2$, input $1$ leads to $q_3$ (non-accepting), whereas from $q_0$ and $q_1$, input $1$ leads to accepting states. Thus, $q_2$ is distinguishable.
• From $q_1$, input $11$ leads to $q_3$ (non-accepting), whereas from $q_0$, input $11$ leads to $q_2$ (accepting). Thus, $q_1$ and $q_0$ are distinguishable.

Since all 4 states are pairwise distinguishable, the minimum number of states in the DFA is 4.