O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

images

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 ( ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required