GATE CS 2016 Set 2 Q.26 (CS Q.16): Regular Expressions, Finite Automata and Regular Languages

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

(0 + 1)^* (0 + 1)(0 + 1)^*

is ________.

Your answer

Official answer and solution

Solution

Identify the language denoted by the regular expression and construct the minimal state DFA.

The given regular expression is:

R = (0 + 1)^* (0 + 1)(0 + 1)^*

Here, $(0 + 1)^*$ generates any binary string of length $\ge 0$ . The middle term $(0 + 1)$ requires at least one symbol (0 or 1) to be present.

Therefore, $R$ generates the language of all binary strings of length at least 1:

L = \Sigma^+ = \Sigma^* \setminus \{\varepsilon\}

Construct the minimal DFA for $L = \Sigma^+$ over $\Sigma = \{0, 1\}$ :

Start state $q_0$ (non-accepting): represents the empty string $\varepsilon$ . On reading 0 or 1, it transitions to $q_1$ .
State $q_1$ (accepting): represents any string of length $\ge 1$ . On reading 0 or 1, it stays in $q_1$ (self-loop).

Both states are reachable and non-equivalent ( $q_0$ is non-accepting and $q_1$ is accepting). Hence, the minimum sized DFA has exactly 2 states.

Final answer

Common trap

Constructing an NFA with 3 states and not minimizing the resulting DFA.

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

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