[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 sigma = {a, b, c}.
All strings containing exactly one a.


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
(empty string+a)(empty string+a)(empty string+a)

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

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

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

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:

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)*(empty string+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)*(empty string+a+aa)(b+c)*((b+c)(b+c)*(empty string+a+aa)(b+c)*)*

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


Copyright 1996 by David Matuszek
Last modified Feb 4, 1996