Question

Construct a regular expression that defines the language L (say) containing all the words with either exactly one aba-substring or exactly one bab-substring but not both aba- and bab-substrings. (Hint: For example, the word abab does not belong to L.)

Answer 1

Group 1

Types of words that should be generated:

• aa…ba defined by the regular expression: aa*ba.
• abaaaa… defined by the regular expression: abaa*.
• a(bb)b…(aa)ba - note that the aa -substring and the bb -substring prevent words not belonging to the language to be generated. These words can be generated by the regular expression: abbb*aa
• If all of these types of words are combined then we have:

a(a* + bb b* aa )*baa*

Group 2

Types of words that should be generated:

bb…ab defined by the regular expression: bb*ab.

babbbb… defined by the regular expression: babb*.

a(aa)a…(bb)ab - note that the aa-substring and the bb-substring prevent words not belonging to the language from being generated. These words can be generated by the regular expression: a(aa)a*(bb)ab.

If all of these types of words are combined then we have:

b(b* + aa a* bb )*abb*

Thus a regular expression that generates all the words in the required language is:

a(a* + bbb*aa)*baa* + b(b* + aaa*bb)*abb*