Question

The length of the shortest string NOT in the language (over ∑ = {a, b}) of the following regular expression is _______

a *b* (ba)* a*

Answer 1

For the language L = a *b* (ba)* a*

Strings of length 0 = null ∈ L

Strings of length 1 = {a, b} ∈ L

Strings of length 2 = {aa, ab, ba, bb} ∈ L

Strings of length 3 = {aaa, aab, aba, baa, abb, bba, bbb} ∈ L but {bab} ∉ L

The length of the shortest string NOT in the given language is 3.