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*^{118} 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 ( ...

Start Free Trial

No credit card required