Question

The alphabet is Ʃ = {a,b}. Give regular expressions that generate the following languages below. Use these symbols: Ʃ, a, b, ε, Ø, *, (, ), U.

1) ? = {? | ? contains an odd number of a's and ends with b}

2) ? = {a? b? | ? < 5,? < ?}

3) ? = {? | ? contains the substring ab and contains the substring ba}

4) ? = {? | ? has an odd number of a's and exactly two b's}

Answer 1

1) b^*a(b^*ab^*ab^*)^*b^*

It can start with a or b.So, b*a

To ensure it contains odd number of a, a(aa)*. But b may come inside a. So, a(b^*ab^*ab^*)^* .

It ends with any number of b. So,b*

2) ( a+ aa + aaa+ aaaa)(b+ bb +bbb)

i<5, so, i may be 1 or 2 or 3 or 4 but not 5.

j<i, so, j may be 1 or 2 or 3 but not 4.

3) (a+b)^*(ab)(a+b)^*(ba)(a+b)^*

The start and end may be combinations of a and b. So, (a+b)*

It contains substring (ab) and (ba)

It may have combinations of a and b between substring.

4) a(aa)^* bb

It has odd number of a's. So, a(aa)*

It ends with bb. So bb.