Question

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

$a^{\ast }{b}^{\ast }(ba{)}^{\ast }{a}^{\ast }$

• A. 3

Answer 1

The correct option is A 3
Check the string one-by-one starting from $ϵ$, a, b, aa, ab, ba, bb,... until we reach the first string that is not generated by the given regular expression $a^{\ast }{b}^{\ast }(ba{)}^{\ast }{a}^{\ast }$.

In this case smallest string NOT generated by the given regular expression is 'bab' whose length is 3.