Unrestricted grammar

In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty. This grammar class can generate arbitrary recursively enumerable languages. An unrestricted grammar is a formal grammar , where is a finite set of nonterminal symbols, is a finite set of terminal symbols with and disjoint, is a finite set of production rules of the form where and are strings of symbols in and is not the empty string, and is a specially designated start symbol. As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have. The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar there exists some Turing machine capable of recognizing and vice versa. Given an unrestricted grammar, such a Turing machine is simple enough to construct, as a two-tape nondeterministic Turing machine. The first tape contains the input word to be tested, and the second tape is used by the machine to generate sentential forms from . The Turing machine then does the following: Start at the left of the second tape and repeatedly choose to move right or select the current position on the tape. Nondeterministically choose a production from the productions in . If appears at some position on the second tape, replace by at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of and (e.g. if is longer than , shift the tape symbols left). Compare the resulting sentential form on tape 2 to the word on tape 1. If they match, then the Turing machine accepts the word. If they don't, the Turing machine will go back to step 1. It is easy to see that this Turing machine will generate all and only the sentential forms of on its second tape after the last step is executed an arbitrary number of times, thus the language must be recursively enumerable.