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*