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: