Theory of Computation

3.3   REGULAR EXPRESSIONS

There is a very useful alternative (to FA and NFA) way to finitely represent the L(M)-sets via a system of notation, or naming, that is called regular expressions. Regular expressions are familiar to users of the UNIX operating system. They are more than “just names” as they embody enough information—as we will see—to be mechanically transformable into a NFA (and via Theorem 3.2.1.4 to a FA).

3.3.0.7 Definition. (Regular Expressions over Σ) Given the alphabet Σ, we form the extended alphabet

where the symbols , +, ·, *, (,) (not including the comma separators) are all abstract or formal¹¹⁸ and do not occur in Σ. In particular, “” in this alphabet is just a symbol, and so are “+”, “·”, “*”, and the brackets. All these symbols will be interpreted shortly.

The set of regular expressions over Σ is a set of strings over the augmented alphabet above, given as the closure Cl(, ), where

= Σ ∪{}

and contains three operations

(1) From strings α and β form the string ( ...