The length of the shortest string NOT in the language (over \(Σ = \{ a,b \}\))…

Answer: 3

Check all shorter lengths:

• Length 0: the empty string is in the language because each starred part can be empty.

• Length 1: "a" is produced by the leading a*, and "b" is produced by the b*.

• Length 2: all four length-2 strings are in the language: "aa" from a*, "ab" from a* then b*, "ba" from one repetition of "ba" in (ba)*, and "bb" from b*.

Now show there exists a string of length 3 not in the language.

Consider the string "bab".

• Any string in the language has the form a^i b^j (ba)^k a^l. If k = 0 then the string is a block of a's, then a block of b's, then a block of a's (all b's are contiguous). The pattern "b a b" has two b's separated by an a, so it cannot arise when k = 0.

• If k ≥ 1 then (ba)^k contributes pairs "ba"; every b inside the (ba)* part is immediately followed by an a. After producing those pairs, any trailing a* only adds a's. Hence any b that appears after an a in this decomposition would need to be followed by a, so the string cannot end with a b following an a. The string "bab" ends with b after an a, so it cannot arise when k ≥ 1 either.

Thus "bab" is not in the language, and since all shorter strings are in the language, the length of the shortest string not in the language is 3.