GATE CS 2017 Set 1 Q22 — Regular Expressions and Finite Automata

The given regular expression is $L = (a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. This language consists of all strings where the second symbol from the right end is $b$.

In general, a deterministic finite automaton (DFA) that recognizes the language of strings where the $k$-th symbol from the right is a specific character requires at least $2^k$ states. Here, $k = 2$, so the minimum number of states is $2^2 = 4$.

We can construct the minimal DFA with the following 4 states representing the history of the last two symbols read:

• $q_0$ (Start state): Represents having read nothing, or ending in $aa$.
• $q_1$: Represents ending in $ab$.
• $q_2$ (Accepting state): Represents ending in $ba$.
• $q_3$ (Accepting state): Represents ending in $bb$.

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