Regular Expressions

1. 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.
2. If a is a symbol in alphabet, then a is a regular expression that denotes {a}, that is, the set containing the string a.
3. Suppose r and s are regular expression denoting the languages L(r) and L(s). Then
   1. (r)|(s) is a regular expression denoting L(r) U L(s).
   2. (r)(s) is a regular expression denoting L(r) L(s).
   3. (r)* is a regular expression denoting (L(r))*.
   4. (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.