[Overview] [Previous] [Next]

# Example Regular Expressions

These are from exercise 14 on page 78 of your textbook.
Give regular expressions for the following languages on = {a, b, c}.
All strings containing exactly one a.

(b+c)*a(b+c)*

All strings containing no more than three a's.

We can describe the string containing zero, one, two, or three a's (and nothing else) as
(+a)(+a)(+a)

Now we want to allow arbitrary strings not containing a's at the places marked by X's:
X(+a)X(+a)X(+a)X

so we put in (b+c)* for each X:
(b+c)*(+a)(b+c)*(+a)(b+c)*(+a)(b+c)*

All strings which contain at least one occurrence of each symbol in .

The problem here is that we cannot assume the symbols are in any particular order. We have no way of saying "in any order", so we have to list the possible orders:
abc+acb+bac+bca+cab+cba

To make it easier to see what's happening, let's put an X in every place we want to allow an arbitrary string:
XaXbXcX + XaXcXbX + XbXaXcX + XbXcXaX + XcXaXbX + XcXbXaX

Finally, replacing the X's with (a+b+c)* gives the final (unwieldy) answer:
(a+b+c)*a(a+b+c)*b(a+b+c)*c(a+b+c)* + (a+b+c)*a(a+b+c)*c(a+b+c)*b(a+b+c)* + (a+b+c)*b(a+b+c)*a(a+b+c)*c(a+b+c)* + (a+b+c)*b(a+b+c)*c(a+b+c)*a(a+b+c)* + (a+b+c)*c(a+b+c)*a(a+b+c)*b(a+b+c)* + (a+b+c)*c(a+b+c)*b(a+b+c)*a(a+b+c)*

All strings which contain no runs of a's of length greater than two.

We can fairly easily build an expression containing no a, one a, or one aa:
(b+c)*(+a+aa)(b+c)*

but if we want to repeat this, we need to be sure to have at least one non-a between repetitions:
(b+c)*(+a+aa)(b+c)*((b+c)(b+c)*(+a+aa)(b+c)*)*

All strings in which all runs of a's have lengths that are multiples of three.

(aaa+b+c)*