Question

Consider the regular expression ? = b(ba U aab)*(b U a*). In lexicographical order (shorter strings before longer strings, alphabetical order for strings of the same length), give the 8 shortest strings in the language generated by ?.

Answer 1

Solution:-

Using the Regular expression ? = b(ba U aab)*(b U a*) the 8 shortest strings which would be in the language generated by ? are as follows:-

1) 'b' it can be generated as b(epsilon)(epsilon)
2) 'ba' it can be generated as b(epsilon)(a)
3) 'bb' it can be generated as b(epsilon)(b)
4) 'baa' it can be generated as b(epsilon)(aa)
5) 'bba' it can be generated as b(ba)(epsilon)
6) 'baaa' it can be generated as b(epsilon)(aaa)
7) 'baab' it can be generated as b(aab)(epsilon)
8) 'bbaa' it can be generated as b(ba)(a)