An Introduction to Formal Languages and Automata, 7th Edition

11.2 UNRESTRICTED GRAMMARS

To investigate the connection between recursively enumerable languages and grammars, we return to the general definition of a grammar in Chapter 1. In Definition 1.1 the production rules were allowed to take any form, but various restrictions were later made to get specific grammar types. If we take the general form and impose no restrictions, we get unrestricted grammars.

DEFINITION 11.3

A grammar G = (V, T, S, P) is called unrestricted if all the productions are of the form

$$u\to v,$$

where u is in (V ∪ T)⁺ and v is in (V ∪ T)^*.

In an unrestricted grammar, essentially no conditions are imposed on the productions. Any number of variables and terminals can be on the left or right, and these can occur in any order. There ...