GATE CS 2014 Set 3 Q15 — Regular Expressions and Finite Automata

To find the length of the shortest string not in the language of the regular expression $R = a^*b^*(ba)^*a^*$, we can test strings of increasing lengths over $\Sigma = \{a, b\}$:

• Length 0: $\epsilon$ is in $L(R)$ (by choosing $a^0 b^0 (ba)^0 a^0$).
• Length 1:
  • $a = a^1 b^0 (ba)^0 a^0 \in L(R)$
  • $b = a^0 b^1 (ba)^0 a^0 \in L(R)$
• Length 2:
  • $aa = a^2 b^0 (ba)^0 a^0 \in L(R)$
  • $ab = a^1 b^1 (ba)^0 a^0 \in L(R)$
  • $ba = a^0 b^0 (ba)^1 a^0 \in L(R)$
  • $bb = a^0 b^2 (ba)^0 a^0 \in L(R)$

Since all strings of length $\le 2$ are in $L(R)$, the shortest string not in $L(R)$ must have a length of at least $3$. Let us test the string $bab$ of length 3:

Suppose $bab \in L(R)$. Then $bab = w_1 w_2 w_3 w_4$ where $w_1 \in a^*$, $w_2 \in b^*$, $w_3 \in (ba)^*$, and $w_4 \in a^*$.

• Since $bab$ starts with $b$, we must have $w_1 = \epsilon$.
• Since $bab$ ends with $b$, we must have $w_4 = \epsilon$.
• This simplifies the match to $bab = w_2 w_3$ where $w_2 \in b^*$ and $w_3 \in (ba)^*$.
• If $w_3 = \epsilon$, then $bab = w_2 \in b^*$, which is false.
• If $w_3 = ba$, then $bab = w_2 ba \implies w_2 = b$, giving $bba \neq bab$.
• If $|w_3| \ge 4$, the length exceeds 3.

Thus, $bab \notin L(R)$. The length of the shortest string not in the language is 3.