GATE CS 2016 Set 2 Q16 — Regular Expressions and Finite Automata

The given regular expression is:

$$L = (0+1)^{*} (0+1) (0+1)^{*}$$

Let us analyze the language $L$ over the alphabet $\Sigma = \{0, 1\}$:

• $(0+1)^*$ represents any string of $0$s and $1$s (including the empty string $\epsilon$).
• $(0+1)$ represents a single symbol, either $0$ or $1$.

Thus, the regular expression defines the language of all non-empty strings over $\Sigma$. That is, $L = \Sigma^+ = \Sigma^* \setminus \{\epsilon\}$.

DFA Construction:

To accept all non-empty strings, we need:

1. An initial state $q_0$ (non-accepting) because the empty string $\epsilon \notin L$.
2. On receiving the first input symbol ($0$ or $1$), the transition goes to an accepting state $q_1$.
3. Once in $q_1$, any subsequent input ($0$ or $1$) keeps the automaton in $q_1$.

The transition table for this DFA is:

Minimality:

Since $L$ is neither empty ($L \neq \emptyset$) nor contains all strings ($L \neq \Sigma^*$), any DFA accepting $L$ must have at least one accepting state and at least one non-accepting state. Therefore, the minimum number of states required is $2$.