Submitted by Paul on Sun, 10/13/2013 - 04:09

### Definition of Regular Expressions

The class of regular expression over an alphabet Σ is defined recursively by:

Rule 1)
Any σ∈Σ can be regarded as a regular expression.
The empty string ε is a regular expression.
The empty set ∅ is a regular expression.
Rule 2)
if φ is a regular expression then so are:
(φ)
φ* with the understanding that ∅*=∅
if φ and ψ are regular expression then so are:
φ∪ψ
φψ
Rule 3)
No expression is a regular expression unless it can be generated by finite
application of Rules 1 and 2.