Constructing Regular Expressions

What are the rules for constructing a regular expression? They are pretty simple.

Example of Regular Expression Construction

Suppose we have the set A = {a, b, c} to work with. Then we use

• a to be the regular expression that stands for the set {a},
• b to be the regular expression that stands for the set {b}, and
• c to be the regular expression that stands for the set {c}.

We also have two other special regular expresssions:

• ε, the regular expression that stands for {ε}, the set that contains just the empty string, and
• ∅, the regular expression that stands for {}, the empty set.

Any expressions we can build up from these base regular expressions with a finite number of applications of the operators

• "|"
• concatenation
• and *

(with the use of parentheses to enforce operation order) are also regular expressions.

So, for example,

• a is the regular expression that stands for the set {a}.
• a | b is the regular expression that stands for the set {a} union {b} = {a, b}.
• (a | b)* is the regular expression that stands for the set {a. b}* = { ε, a, b, aa, ab, ba, bb, aaa, aab, ...}
• (a | b*) is the regular expression that stands for the set {a, ε, b, bb, bbb, ...}

and so forth.