GATE CS 2023 Q.63: Regular Expressions, Finite Automata and Regular Languages

Consider the language $L$ over the alphabet $\{0, 1\}$ , given below:

L = \{w \in \{0, 1\}^* \mid w \text{ does not contain three or more consecutive 1's}\}.

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is _______.

Your answer

Official answer and solution

Official answer: 4
From: Official GATE 2023 answer key

Solution

Construct the minimal DFA that rejects any string containing the substring 111.

The language $L$ consists of all binary strings that do not contain the substring $111$ . A minimal DFA tracks the number of consecutive $1$ 's read immediately preceding the current position:

State $q_0$ : 0 consecutive $1$ $1$ 's seen (Start state, Accepting).
- On $0 \to q_0$
- On $1 \to q_1$
State $q_1$ : 1 consecutive $1$ $1$ seen (Accepting).
- On $0 \to q_0$
- On $1 \to q_2$
State $q_2$ : 2 consecutive $1$ $1$ 's seen (Accepting).
- On $0 \to q_0$
- On $1 \to q_3$
State $q_3$ : 3 consecutive $1$ $1$ 's seen (Dead/Trap state, Non-accepting).
- On $0 \to q_3$
- On $1 \to q_3$

These 4 states are pairwise distinguishable by suffix distinguishing extensions (e.g., $11$ distinguishes $q_1$ from $q_0$ ). By the Myhill-Nerode theorem, this DFA is minimal, having 4 states.

Final answer

Common trap

Omitting the dead/trap state $q_3$ , which is mandatory in a complete Deterministic Finite-State Automaton.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 63 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source