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.4   REGULAR GRAMMARS AND LANGUAGES

There is yet another way to finitely represent a regular set: by a grammar—which will naturally be called a regular grammar. To motivate the core idea behind grammars, consider, for example, the (inductive) definition of formulae (2.11.0.27). Moreover, to simplify matters, let us stay in the Boolean domain—that is, we will include only the connectives ¬ and ∨ but no quantifiers—and we will also adopt as atomic formulae the set of Boolean variables,121 generated by the symbol p with or without primes. Thus, the atomic formulae include

p, p′, p‴, p(n)

where p(n) indicates p with n primes

images

The alphabet over which we build these simplified well-formed (Boolean) formulae is

(,), ¬, ∨, p, p′, p″, p‴, . . .

In the inductive clauses of 2.11.0.27 we have included “if images and images are formulae, then so is (imagesimages)”. In words this says that

One way to get a “complicated” formula is to take two formulae, and join themvia a “∨”, adding outermost brackets after that.

This generates ...

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