GATE CS 2015 Set 2 Q53 — Regular Expressions and Finite Automata

The given regular expression is $(0+1)^* (10)$, which represents the language $L$ of all binary strings over $\{0, 1\}$ that end with the substring "$10$".

To find the number of states in the minimal DFA, we can define the states based on the longest suffix of the input read so far that matches a prefix of "$10$":

• State $A$ (Start State): The string read so far does not end with '$1$' or '$10$'.
• State $B$: The string read so far ends with '$1$'.
• State $C$ (Accepting State): The string read so far ends with '$10$'.

The transition table for these states is as follows:

Minimality Verification:

• State $C$ is an accepting state, whereas $A$ and $B$ are non-accepting states. Thus, $C$ is distinguishable from both $A$ and $B$.
• States $A$ and $B$ are distinguishable because on input $0$, state $B$ transitions to the accepting state $C$, while state $A$ transitions to the non-accepting state $A$.

Since all $3$ states are pairwise distinguishable, the minimal DFA has exactly $3$ states.