Regular Expressions

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.