Question

1. All questions assume the alphabet Σ = { a , b }.

a) Give a regular expression representing the language of all strings containing abab as a substring.

b) Give a regular expression representing the language of all strings with an even number of a's or an odd number of b's, such as abab or baabaab.

c) Give a regular expression representing the language of all strings of the form a^mbⁿ, where m is even and n is odd. Observe that all the a's come before all the b's, which is different than the previous 2 questions. Sample strings are aab, aabbb, aaaab, and bbbbb. (Remember that 0 is even).

d) List the first 10 strings in canonical order of the language in question b above (even number of a's or odd number of b's, where the a's and b's can occur in any order).

e) List the first 10 strings in canonical order of the language in question c above (a^mbⁿ).

Answer 1

1. [ab]*abab[ab]* - Any number of valid characters before and after 'abab'

2. b*[ab*ab*]* | a*ba*[ba*ba*]* The sub-expression on the left is for even number of 'a's and the one on the right is for odd number of 'b's.

b*[ab*ab*]* - represents any number of 'b's followed by even number (including 0, 2, 4 etc) of 'a's. The 'a's are separated from each other by zero or more 'b' on both sides.

The expression for odd 'b's is very similar except that there is a mandatory 'b', with any number of 'a's on each side; this is then followed by an expression representing an even number of 'b's.

3. [aa]*b[bb]* - this is a pair of 'a's repeated any number of times - to provide an even count of 'a's followed by one b and then an even number of 'b's - so that we totally have an odd number of 'b's.

4. 10 basic valid strings are b, aba, baa, ababb, babab, abababa, bbabab, aabaababa, bbabbabb, aabaababa - not sure about canonical order though.

5. 10 valid strings are b, aab, aabbb, aaaab, aaaabbb, aaaaaab, aaaaaabbb, aaaabbbbb, aaaaaabbbbb, aaaaaaaab - again, not sure about canonical order, you will have to excuse that. Could not find ANY online references to canonical forms for regular expression strings.