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 to a FA). Definition. (Regular Expressions over Σ) Given the alphabet Σ, we form the extended alphabet


where the symbols images, +, ·, *, (,) (not including the comma separators) are all abstract or formal118 and do not occur in Σ. In particular, “images” 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(images, images), where

= Σ ∪{}

and contains three operations

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

Get Theory of Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.