Unrestricted grammar

In formal language theory, the class of unrestricted grammars (also called semi-Thue, type 0, or phrase structure grammars by some authors) is the most general class of grammars in the Chomsky–Schützenberger hierarchy. On the productions of an unrestricted grammar, no other restrictions are made than each of their left-hand sides being non-empty.:220 This grammar class can generate arbitrary recursively enumerable languages. In formal language theory, the class of unrestricted grammars (also called semi-Thue, type 0, or phrase structure grammars by some authors) is the most general class of grammars in the Chomsky–Schützenberger hierarchy. On the productions of an unrestricted grammar, no other restrictions are made than each of their left-hand sides being non-empty.:220 This grammar class can generate arbitrary recursively enumerable languages. An unrestricted grammar is a formal grammar G = ( N , Σ , P , S ) {displaystyle G=(N,Sigma ,P,S)} , where N {displaystyle N} is a set of nonterminal symbols, Σ {displaystyle Sigma } is a set of terminal symbols, N {displaystyle N} and Σ {displaystyle Sigma } are disjoint, P {displaystyle P} is a set of production rules of the form α → β {displaystyle alpha o eta } where α {displaystyle alpha } and β {displaystyle eta } are strings of symbols in N ∪ Σ {displaystyle Ncup Sigma } and α {displaystyle alpha } is not the empty string, and S ∈ N {displaystyle Sin N} is a specially designated start symbol.:220 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 G {displaystyle G} there exists some Turing machine capable of recognizing L ( G ) {displaystyle L(G)} and vice versa. Given an unrestricted grammar, such a Turing machine is simple enough to construct, as a two-tape nondeterministic Turing machine.:221 The first tape contains the input word w {displaystyle w} to be tested, and the second tape is used by the machine to generate sentential forms from G {displaystyle G} . The Turing machine then does the following: It is easy to see that this Turing machine will generate all and only the sentential forms of G {displaystyle G} on its second tape after the last step is executed an arbitrary number of times, thus the language L ( G ) {displaystyle L(G)} must be recursively enumerable. The reverse construction is also possible. Given some Turing machine, it is possible to create an equivalent unrestricted grammar:222 which even uses only productions with one or more non-terminal symbols on their left-hand sides. Therefore, an arbitrary unrestricted grammar can always be equivalently converted to obey the latter form, by converting it to a Turing machine and back again. Some authors use the latter form as definition of unrestricted grammar. The decision problem of whether a given string s {displaystyle s} can be generated by a given unrestricted grammar is equivalent to the problem of whether it can be accepted by the Turing machine equivalent to the grammar. The latter problem is called the Halting problem and is undecidable. Recursively enumerable languages are closed under Kleene star, concatenation, union, and intersection, but not under set difference; see Recursively enumerable language#Closure properties. The equivalence of unrestricted grammars to Turing machines implies the existence of a universal unrestricted grammar, a grammar capable of accepting any other unrestricted grammar's language given a description of the language. For this reason, it is theoretically possible to build a programming language based on unrestricted grammars (e.g. Thue).