GATE 2014 CS (CS3) – Question 25
Over $\Sigma=\{a,b\}$, find the length of the shortest string NOT in the language of $a^*b^*(ba)^*a^*$.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3 to 3
Explanation
All strings of lengths0,1,2fit the expression. The length3string babdoes not: after using ba, its final b cannot be placed in the trailing a*or another complete ba. Therefore the shortest excluded length is **3**. Other length3strings such as abaare accepted.