Regular Expressions (RE): Definition
2/29
 Gist:
Expressions with operators ., +, and * that denote concatenation, union, and iteration, respectively.
Definition: Let S be an alphabet. The regular expressions over S and the languages they denote are defined as follows:
• Æ is a RE denoting the empty set
• e  is a RE denoting {e}
• a, where a Î S, is a RE denoting {a}
• Let r and s be regular expressions denoting the  languages Lr and Ls, respectively; then
• (r.s) is a RE denoting L = Lr Ls
•  (r + s) is a RE denoting L = Lr È  Ls
•  (r*) is a RE denoting L = Lr*