Building Regular Expressions

Zero or more.

a* means "zero or more a's." To say "zero or more ab's," that is, {, 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+).

Any string at all.

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

Any nonempty string.

This can be written as any character from 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 = {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)*.