Question 25

Given regular expression $R = a^* b^* (ba)^* a^*$.

1. Length 0:

   • $\epsilon$: generated with exponents $0, 0, 0, 0$ ($a^0 b^0 (ba)^0 a^0 = \epsilon$).

2. Length 1:

   • $a$: $a^1 b^0 (ba)^0 a^0 = a$.
   • $b$: $a^0 b^1 (ba)^0 a^0 = b$.
     All length-1 strings are generated.

3. Length 2:

   • $aa$: $a^2 b^0 (ba)^0 a^0 = aa$.
   • $ab$: $a^1 b^1 (ba)^0 a^0 = ab$.
   • $ba$: $a^0 b^0 (ba)^1 a^0 = ba$.
   • $bb$: $a^0 b^2 (ba)^0 a^0 = bb$.
     All length-2 strings are generated.

4. Length 3:

   • $aaa$: $a^3 \in L$.
   • $aab$: $a^2 b^1 \in L$.
   • $aba$: $a^1 b^0 (ba)^1 a^0 = aba \in L$.
   • $abb$: $a^1 b^2 \in L$.
   • $baa$: $a^0 b^0 (ba)^1 a^1 = baa \in L$.
   • $bba$: $a^0 b^2 (ba)^0 a^1 = bba \in L$.
   • $bbb$: $b^3 \in L$.
   • Now consider $bab$:
     • If the $(ba)^*$ term has exponent $0$, strings have the form $a^* b^* a^*$, where all $b$'s must be contiguous; hence $bab$ cannot be formed.
     • If the $(ba)^*$ term has exponent $\ge 1$, the string ends with $(ba)^k a^m$. Since $(ba)$ ends in $a$ and is followed only by $a^*$, any such string must end with $a$.
     • Since $bab$ ends with $b$, it cannot be formed with $(ba)^k$ for $k \ge 1$.
       Therefore, $bab \notin L(R)$.

5. The string $bab$ has length $3$, and all strings of length $< 3$ are in the language.

Hence, the length of the shortest string NOT in the language is $3$.