## Regular Expressions

###

- The regular expressions over alphabet specifies a language according to
the following rules.
is a regular expression that denotes {},
that is, the set containing the empty string.
- If a is a symbol in alphabet, then a is a regular expression that denotes
{a}, that is, the set containing the string a.
- Suppose r and s are regular expression denoting the languages L(r) and L(s).
Then
- (r)|(s) is a regular expression denoting L(r) U L(s).
- (r)(s) is a regular expression denoting L(r) L(s).
- (r)* is a regular expression denoting (L(r))*.
- (r) is a regular expression denoting L(r), that is, extra pairs of
parentheses may be used around regular expressions.

Unnecessary parenthesis can be avoided in regular expressions using the
following conventions:

- The unary operator * (kleene closure) has the highest precedence and is
left associative.
- Concatenation has a second highest precedence and is left associative.
- Union has lowest precedence and is left associative.

###