Computer science Automata and formal languages Concept
Unrestricted grammar
Summary
An unrestricted grammar is a formal grammar whose rules may replace any string containing a nonterminal by any string. It is the most general kind of generative grammar, called type 0. The languages generated by unrestricted grammars are exactly the recursively enumerable languages, the languages recognised by Turing machines. So grammars of this kind are as powerful as any computer.
Where this leads
1 page builds on this one.
Further reading
About this page
| Tag | 4WNNN9726C |
|---|---|
| URI | m2://4WNNN9726C |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q42, 03D05, 03D10 |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.