Unrestricted grammar
From Wikipedia, the free encyclopedia
In formal language theory, an unrestricted grammar is a formal grammar on which no restrictions are made on the left and right sides of the grammar's productions. This is the most general class of grammars in the Chomsky–Schützenberger hierarchy, and can recognize arbitrary recursively enumerable languages.
Contents |
[edit] Formal definition
An unrestricted grammar is a formal grammar G = (N,Σ,P,S), where N is a set of nonterminal symbols, Σ is a set of terminal symbols, N and Σ are disjoint (actually, this is not strictly necessary, because unrestricted grammars make no real distinction between nonterminal and terminal symbols, the designation exists purely so that one knows when to stop when trying to generate sentential forms of the grammar), P is a 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.
[edit] Unrestricted grammars and Turing machines
It may be shown that unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some Turing machine capable of recognizing 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. The first tape contains the input word w to be tested, and the second tape is used by the machine to generate sentential forms from G. 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 G. - 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 go back to step 1.
It is easy to see that this Turing machine will generate all and only the sentential forms of G on its second tape after the last step is executed an arbitrary number of times, thus the language L(G) must be recursively enumerable.
The reverse construction is also possible. Given some Turing machine, it is possible to create an unrestricted grammar.
[edit] Computational properties
As might be expected from the equivalence of unrestricted grammars and Turing machines, the decision problem of whether a given string s belongs to the language of some unrestricted grammar is in general undecidable.
It is perfectly possible to create a universal unrestricted grammar capable of accepting any other unrestricted grammar's language given a description of the language, just as it is possible to create a universal Turing machine, so it would in theory be possible to build a programming language based on unrestricted grammars.
[edit] References
- John Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation, 1st edition, Addison-Wesley. ISBN 0-201-44124-1. (the Cinderella book)
[edit] See also
| Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
|---|---|---|---|
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| n/a | Indexed | Indexed | Nested stack |
| n/a | Tree-adjoining etc. | (Mildly context-sensitive) | Embedded pushdown |
| Type-2 | Context-free | Context-free | Nondeterministic pushdown |
| n/a | Deterministic context-free | Deterministic context-free | Deterministic pushdown |
| Type-3 | Regular | Regular | Finite |
| n/a | Star-free | Counter-Free | |
| Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it. |
|||
