The length of the shortest string NOT in the language (over $\Sigma = \{a, b\}$) of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$

Let the given regular expression be $R = a^*b^*(ba)^*a^*$.

Let us test strings generated by $R$ of various lengths:

1. Length 0:

   • $\epsilon$ is generated by choosing all exponents as $0$.

2. Length 1:

   • $a$: generated by $a^1 b^0 (ba)^0 a^0$

   • $b$: generated by $a^0 b^1 (ba)^0 a^0$

   All strings of length 1 are in $L(R)$.

3. Length 2:

   • $aa$: generated by $a^2$

   • $ab$: generated by $a^1 b^1$

   • $ba$: generated by $(ba)^1$

   • $bb$: generated by $b^2$

   All strings of length 2 are in $L(R)$.

4. Length 3:

   • $aaa$: generated by $a^3$

   • $aab$: generated by $a^2 b^1$

   • $aba$: generated by $a^1 (ba)^1$

   • $abb$: generated by $a^1 b^2$

   • $baa$: generated by $(ba)^1 a^1$

   • $bab$: generated by $b^1 (ba)^1$

   • $bba$: generated by $b^2 a^1$ (via $b^2 (ba)^0 a^1$)

   • $bbb$: generated by $b^3$

   Wait, let's check $bab$: To form $bab$, we could try:

   • $a^*b^*(ba)^*a^*$: if we pick $b^1$ from $b^*$ and $a^1$ from $(ba)^*$, that gives $ba$, followed by $b$? But $(ba)^*$ only gives strings with alternating $ba$.

   • Let us check if $bab$ can be generated:

     • If from $(ba)^*$ we pick $(ba)^1 = ba$, we have $a^*b^*(ba)a^*$. To make $bab$, the last letter must be $b$, but after $(ba)$ only $a^*$ is available, which cannot produce $b$.

     • If $(ba)^*$ is $\epsilon$, we have $a^*b^*a^*$, which cannot produce $bab$ since the pattern is $a\dots ab\dots ba\dots a$ (contains at most one transition from $b$ to $a$, and no $b$ after the final $a$'s).

   • Thus, $bab$ cannot be generated by $a^*b^*(ba)^*a^*$.

Since all strings of length $0, 1, 2$ are in $L(R)$, the length of the shortest string not in the language is 3.