Question

Find the regular expression for the language over inputs {a, b}.

i) The set of all strings ending neither in 'b' nor in ‘ba'

ii) The set of all strings containing at least one 'a' and at least one 'b'

Answer 1

i) (a + b b* a a (b* a b))

ii) (a+b)ab(a+b) + (a+b)ba(a+b)

Answer 2

The regular expression for the language over inputs {a, b} is derived as follows:

i) The set of all strings ending neither in 'b' nor in ‘ba'

The regular expression is: (a + b b* a a (b* a b)*)*

This expression ensures that the string does not end with 'b' or 'ba'. It allows for any number of 'a's and for 'b's that are followed by 'aa' and then optionally by repeating 'b*ab'.

ii) The set of all strings containing at least one 'a' and at least one 'b'

The regular expression is: (a+b)*ab(a+b)* + (a+b)*ba(a+b)*

This expression ensures that the string contains at least one 'a' and at least one 'b' by requiring either the substring 'ab' or the substring 'ba' to be present within any combination of 'a's and 'b's.