The Chomsky Hierarchy, and Where the Aṣṭādhyāyī Sits
Chapter Forty-Five
Syllabus topic Module 1, "Automata theory", "Context-Free Grammar (CFG)"
Pages 147 to 149 of 378
In one line
Grammars fall into four nested classes by how much their rules are allowed to say, and each class has a machine that recognises exactly its languages.
In the wording you can write in an examination: the Chomsky hierarchy classifies formal grammars into four types by restrictions on the form of their productions. Type 3, regular, allows a single non-terminal to rewrite to a terminal optionally followed by a single non-terminal; type 2, context-free, allows any right-hand side but only a single non-terminal on the left; type 1, context-sensitive, allows any left-hand side provided the right-hand side is at least as long; type 0, unrestricted, allows any production. Each class is properly contained in the next, and each corresponds to a class of recognising machine.
The four classes
| Type | Name | Shape of a production | Machine that recognises it |
|---|---|---|---|
| 3 | regular | A rewrites to a, or to a B | finite automaton |
| 2 | context-free | A rewrites to anything | pushdown automaton |
| 1 | context-sensitive | any left side, right side no shorter | linear bounded automaton |
| 0 | unrestricted | any production at all | Turing machine |
The containment is proper. Every regular language is context-free and some context-free languages are not regular; every context-free language is context-sensitive and some context-sensitive ones are not context-free; and so on. So the hierarchy is a real hierarchy and not just a set of labels.
What each class cannot do, which is how you tell them apart
This is the practical content of the hierarchy, and it is what a question will actually ask.
Regular cannot count. The language of strings with equally many a's and b's is not regular, because a finite automaton has finitely many states and cannot remember an unbounded count. Nor can it match nested brackets.
Context-free can count to one depth but cannot compare two. Balanced brackets are context-free. Strings of the form a to the n, b to the n, c to the n, with all three counts equal, are not, because a pushdown automaton has one stack and can compare only one pair.
Context-sensitive can do that, and more. The three-way equality is context-sensitive. What it cannot do is anything requiring unbounded working space beyond the length of the input.
Unrestricted can do anything computable, which also means membership is undecidable in general: there is no procedure that always answers whether a string is in the language.
The costs
The other half of the hierarchy is the price of each level, and it is why nobody uses type 0 for a programming language.
| Type | Deciding membership | Typical use |
|---|---|---|
| 3 | linear time, constant space | lexical analysis, search patterns, tokenising |
| 2 | polynomial time, and linear for the restricted forms compilers use | the syntax of programming languages |
| 1 | decidable, but no efficient general algorithm | rarely used directly |
| 0 | undecidable in general | not used for syntax |
The Chomsky Hierarchy, and Where the Aṣṭādhyāyī Sits
The lesson a language designer takes from this is that expressiveness is not free, and the useful levels are the bottom two. Programming languages are deliberately kept context-free or very nearly so, because a parser for them then exists and is fast.
The placement question, and why this book refuses it
"Where does the Aṣṭādhyāyī sit in the hierarchy?" is asked often and this book does not answer it. The refusal has a reason and the reason is the answer worth writing.
The hierarchy classifies grammars in a fixed formalism. A production is a pair of strings over a fixed alphabet of terminals and non-terminals. To place a system in the hierarchy you must first express it in that formalism.
The Aṣṭādhyāyī is not in that formalism. Its rules refer to markers that are deleted, to whether other rules have operated, and to positions in the text. [Context-Free Grammar, and Whether Pāṇini Wrote One] lists these.
So a placement would be a claim about a formalisation, not about the text. Different formalisations of the same grammar can land in different classes, and the choice of formalisation is where all the content is. A paper that states a class without stating its formalisation has not said anything checkable.
What can be said, and is. Individual mechanisms can be placed, and this book places them.
| Mechanism | What it corresponds to |
|---|---|
| a rule with no context, adding an affix | a context-free production |
| 7.3.84 with its following-affix condition | a context-sensitive production |
| the pratyāhāra device, naming a set of sounds | a character class, which is regular |
| 8.2.1's asiddhatva | a phase boundary, which is outside the hierarchy entirely |
| the four precedence principles | an application strategy, which is outside the hierarchy entirely |
The last two rows are the interesting ones. A strategy for choosing which rule to apply is not part of a grammar in the Chomsky sense at all: a grammar defines a set of strings and says nothing about how they are produced. Pāṇini's system is as much a procedure as a grammar, and the hierarchy has no axis for that.
Worked example: why a strategy is not a grammar
Take two productions that both apply to the same string.
In a context-free grammar this is not a problem and not a choice. Both derivations exist, both results are in the language, and if they produce different structures for the same string the grammar is ambiguous.
In Pāṇini's system it is a problem with a stated answer. Exactly one of the two rules is to apply, the precedence principles say which, and the other result is not a Sanskrit word.
The Chomsky Hierarchy, and Where the Aṣṭādhyāyī Sits
So the two systems differ in what a rule set is for. A Chomsky grammar defines a set. Pāṇini's defines a function, from a root and a meaning to one form. A system that defines a function needs a strategy and a system that defines a set does not, and that is why the hierarchy does not have a place for the strategy.
Quick revision
- Four types: 3 regular, 2 context-free, 1 context-sensitive, 0 unrestricted, each properly contained in the next.
- Machines: finite automaton, pushdown automaton, linear bounded automaton, Turing machine.
- Regular cannot count or match brackets; context-free can match one nesting but not compare two counts; context-sensitive can; unrestricted makes membership undecidable.
- Costs rise with expressiveness, which is why programming languages are kept at type 2 or below.
- This book does not place the Aṣṭādhyāyī in a class, because a placement is a claim about a formalisation and no formalisation of the whole grammar is offered.
- It does place mechanisms: pratyāhāra is regular, a context-free rule is type 2, 7.3.84 is type 1, and asiddhatva and the precedence principles are outside the hierarchy.
- A Chomsky grammar defines a set of strings; Pāṇini's defines a function to one form, which is why it needs a strategy.
Test yourself
1. Name the four types with their production shapes and their machines.
Type 3 regular, a non-terminal rewriting to a terminal or a terminal and a non-terminal, recognised by a finite automaton. Type 2 context-free, one non-terminal on the left, a pushdown automaton. Type 1 context-sensitive, any left side with a right side no shorter, a linear bounded automaton. Type 0 unrestricted, any production, a Turing machine.
2. Give one language each type cannot generate that the next can.
Regular cannot generate balanced brackets, which is context-free. Context-free cannot generate strings with three equal counts, which is context-sensitive. Context-sensitive cannot generate every computably enumerable language, which type 0 can.
3. Why does this book refuse to place the Aṣṭādhyāyī in the hierarchy?
Because the hierarchy classifies grammars already expressed in one fixed formalism, and the Aṣṭādhyāyī is not in it: its rules refer to deleted markers, to whether other rules have applied, and to positions in the text. A placement would therefore be a claim about a chosen formalisation, and different formalisations land differently.
4. Why are the precedence principles outside the hierarchy altogether?
Because a Chomsky grammar defines a set of strings and says nothing about how a derivation is chosen. Pāṇini's system defines a single correct form, so it needs a strategy for choosing among applicable rules, and the hierarchy has no axis for a strategy.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.