GATE CS 2017 Set 2 Q25 — Regular Expressions and Finite Automata

The given language is $L = \{w_1 a w_2 \mid w_1, w_2 \in \{a,b\}^*, |w_1| = 2, |w_2| \ge 3\}$.

We can simplify the conditions for any string $s \in L$ as follows:

1. The total length of the string must be at least $2 + 1 + 3 = 6$ (i.e., $|s| \ge 6$).
2. The $3^{\text{rd}}$ symbol of the string must be $'a'$.

To construct the minimal DFA, we track the number of symbols read and ensure the $3^{\text{rd}}$ symbol is $'a'$:

• State 0: Start state (0 symbols read).
• State 1: 1 symbol read.
• State 2: 2 symbols read.
• State 3: 3 symbols read, and the $3^{\text{rd}}$ symbol was $'a'$.
• State 4: 4 symbols read (with $3^{\text{rd}}$ symbol $'a'$).
• State 5: 5 symbols read (with $3^{\text{rd}}$ symbol $'a'$).
• State 6: 6 or more symbols read (with $3^{\text{rd}}$ symbol $'a'$). This is the only accepting state.
• Dead State (D): Transitioned to if the $3^{\text{rd}}$ symbol is $'b'$.

Since the minimum length of a string required to reach the accepting state from each of these 8 states is unique ($6, 5, 4, 3, 2, 1, 0,$ and $\infty$ respectively), no two states can be merged. Thus, the DFA is minimal.

Therefore, the minimum number of states is 8.