[Overview] [Previous] [Next]

Building Regular Expressions

Here are some hints on building regular expressions. We will assume sigma = {a, b, c}.

Zero or more.
a* means "zero or more a's." To say "zero or more ab's," that is, {empty string, ab, abab, ababab, ...}, you need to say (ab)*. Don't say ab*, because that denotes the language {a, ab, abb, abbb, abbbb, ...}.

One or more.
Since a* means "zero or more a's", you can use aa* (or equivalently, a*a) to mean "one or more a's." Similarly, to describe "one or more ab's," that is, {ab, abab, ababab, ...}, you can use ab(ab)*.

Zero or one.
You can describe an optional a with (a+empty string).

Any string at all.
To describe any string at all (with sigma = {a, b, c}), you can use (a+b+c)*.

Any nonempty string.
This can be written as any character from sigma followed by any string at all: (a+b+c)(a+b+c)*.

Any string not containing....
To describe any string at all that doesn't contain an a (with sigma = {a, b, c}), you can use (b+c)*.

Any string containing exactly one...
To describe any string that contains exactly one a, put "any string not containing an a," on either side of the a, like this: (b+c)*a(b+c)*.


Copyright 1996 by David Matuszek
Last modified Feb 4, 1996