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)*

Copyright © 1996 by David Matuszek

Last modified Feb 4, 1996