1.2 Chomsky Hierarchy and Recognition Boundaries: How Much Memory Do Rules Need

Learning Objectives

• Accurately identify the four classes of grammars and their corresponding recognition models;
• Understand the containment relationships among language layers;
• Determine which layer typically handles common compilation tasks;
• Avoid conflating actual regular expression dialects, program semantics, and grammar levels.

1. Four Classes of Grammar Are Not Four Programming Languages

Let $V$ be the set of nonterminals and $\mathrm{\Sigma }$ the set of terminals. The hierarchy of grammars ranges from the least restrictive type 0 to the most restrictive type 3:

Type	Core restriction on productions	Corresponding model	Typical languages
3: Regular grammar	Right-linear, such as $A\to aB$ or $A\to a$; alternatively, left-linear forms may be used	Finite automaton	Most character patterns in tokens
2: Context-free grammar	Left side consists of a single non-terminal: $A\to \gamma$	Nondeterministic pushdown automaton (NPDA)	Nested parentheses, expression syntax
1: Context-sensitive grammar	Rules generally do not shorten strings; special cases must handle empty-string productions (ε-rules)	Nondeterministic linear bounded automaton	$\{a^n{b}^n{c}^n\mid n\ge 1\}$
0: Unrestricted grammar	Left side must contain at least one non-terminal; otherwise, no restrictions apply	Turing machine	Recursively enumerable languages

Type 3 also needs an empty-string convention, such as allowing A → ε in a right-linear grammar. Under the noncontracting definition of type 1, S → ε may be allowed if the start symbol never occurs on a right-hand side. The containment chain below uses standard conventions that permit the empty string.

Nondeterminism matters here. NPDAs recognize all context-free languages, while deterministic PDAs recognize a strict subset. General context-sensitive languages correspond to nondeterministic linear bounded automata.

Language classes form a strict containment hierarchy:

$$\text{Regular}⊊\text{Context-Free}⊊\text{Context-Sensitive}⊊\text{Recursively Enumerable}.$$

The more to the left a class is, the more restricted its expressive power, and typically the easier it is to implement efficient, predictable parsing algorithms. The more to the right, it does not follow that such grammars are "better for all tasks."

2. A Finite State Can Only Remember a Finite History

A finite automaton's memory is limited to its current state. Since the number of states is fixed, it can only remember:

• Whether it has seen a particular symbol before;
• The count modulo a fixed integer;
• Whether a finite pattern prefix has been matched.

For example, to recognize that the number of 1 in a binary string is even, only two states are needed: even and odd. Each time a 1 is read, the state switches; reading a 0 leaves the state unchanged.

However, the language

$$L=\{a^n{b}^n\mid n\ge 0\}$$

requires storing an arbitrarily large value of $n$. A finite state machine cannot maintain distinct memory for every possible $n$, so this language is not regular.

3. The Pumping Lemma Provides a Proof by Contradiction

The Pumping Lemma for regular languages states that if $L$ is a regular language, then there exists a pumping length $p$ such that any string $w\in L$ with $|w|\ge p$ can be divided into $w=xyz$ satisfying:

1. $|xy|\le p$;
2. $|y|>0$;
3. For all $i\ge 0$, $x{y}^{i}z\in L$.

For the string $a^p{b}^p$, since the first $p$ characters are all a, the substring $y$ must consist only of a. Every split satisfying the first two constraints puts one or more a characters in $y$. Removing $y$, with $i=0$, changes the number of a characters without altering the number of b characters, resulting in a string that is no longer in $L$, leading to a contradiction.

Keep the quantifiers in order: assume an arbitrary pumping length $p$, choose a suitable $w$, cover every permitted split, and then choose an $i$ that leaves the language. One failed split of your own choosing does not prove nonregularity.

The Pumping Lemma is a necessary condition for a language to be regular, not a sufficient one. The inability to find a counterexample does not prove that a language is regular; to establish regularity, one typically constructs a regular expression, a regular grammar, or a finite automaton directly.

4. Stacks Can Handle a Class of Nested Structures

A pushdown automaton extends a finite automaton with a stack. When it encounters a left parenthesis, it pushes it onto the stack; when it sees a right parenthesis, it pops from the stack. This handles any finite nesting depth, provided the automaton rejects a closing parenthesis on an empty stack and accepts only when the stack returns to its initial state at end of input.

"Stacks can count" is merely intuitive. A stack's access is constrained by last-in, first-out (LIFO) behavior, and it cannot handle all languages involving multiple counters. For example, the language $a^n{b}^n{c}^n$ is not context-free; a single PDA cannot simultaneously maintain the equality of three separate counts.

Context-free grammars are well-suited for describing recursive syntactic structures in programs. However, constraints such as name resolution, type consistency, and the rule that "variables must be declared before use" typically require symbol tables, attribute grammars, or specialized semantic algorithms.

5. The Compiler Stages Do Not Equate to Hierarchical Language Evolution

An outdated summary often reads:

Lexical analysis → Regular languages
Syntactic analysis → Context-free languages
Semantic analysis → Context-sensitive languages
Code generation → Turing machines

The first two are useful approximations, but the last two can be misleading. Semantic analysis indeed involves context dependence, yet modern type systems, name resolution, and control-flow analysis are not simply running a context-sensitive grammar recognizer. Code generation isn't because it "belongs to type 0 grammars"; it's a transformation process that preserves program semantics.

A more accurate engineering layering is:

Stage	Primary Input	Common Models or Structures
Lexical analysis	Characters	Regular expressions, finite automata, hand-written scanners
Syntactic analysis	Tokens	Context-free grammars (CFGs), LL/LR, PEG, abstract syntax trees (ASTs)
Semantic analysis	AST and environment	Symbol tables, type rules, data flow analysis
Intermediate representation and optimization	IR	Control flow graphs (also abbreviated CFGs), SSA, lattices and fixed-point algorithms
Code generation	IR and target information	Instruction selection, scheduling, register allocation

The theoretical hierarchy helps us understand expressive limits, but it cannot replace the actual algorithmic design of specific compiler stages.

6. "Regular expressions" don't necessarily describe regular languages

Classic regular expressions, built from operations like concatenation, alternation, and Kleene star, precisely define regular languages. However, real-world tools often add extra features:

• Backreferences can extend beyond the scope of regular languages;
• Lookarounds alter matching conditions and implementation strategies; conventional lookarounds built from regular subpatterns need not exceed regular-language expressiveness;
• Recursive patterns can express certain nested structures;
• Backtracking engines may suffer exponential runtime performance.

Thus, "using regex" does not imply "executed in linear time by a DFA." The actual behavior depends on the specific dialect, engine, and pattern. Lexical analyzer generators typically restrict rule syntax to ensure deterministic longest match, precedence, and execution efficiency.

7. Recognition, Decision, and Generation

• Recognition: A language recognizer accepts input if it belongs to the language; if not, it may reject the input or run indefinitely.
• Decision: For every input, the system halts within a finite time and correctly determines whether the input belongs to the language or not.
• Generation: A generator produces strings of the language through a set of rules or a defined process.

Finite automata and common CFG parsers halt on finite inputs, making them suitable for decision processes. Here, "common CFG parsers" means algorithms that guarantee termination. Naive recursive descent can loop on left-recursive grammars. At the Turing machine level, it becomes essential to distinguish between recognizability and decidability; this boundary is illustrated in Chapter 4 through the halting problem.

Common Misconceptions

• The higher the level, the more advanced it is: Constrained models are often easier to analyze, verify, and execute efficiently.
• Context-free grammars can express all rules of a programming language: They primarily capture the syntactic skeleton and do not cover full static or dynamic semantics.
• All regular expressions can be compiled into a DFA: This holds only for expressions that define regular languages.
• The pumping lemma can prove a language is regular: It is actually used to demonstrate that certain languages are not regular.

Exercise

1. Design three finite states for the condition "the count of 1 modulo 3 equals 0".
2. Explain why a bracketed language with finite maximum nesting depth is regular, while the version permitting arbitrary finite depth is not.
3. Provide one example each for lexical, syntactic, and semantic constraints, and specify the appropriate processing phase for each.
4. Investigate your regular expression engine to confirm whether it supports backreferences and whether it guarantees linear time complexity.

Summary

The hierarchy describes the computation needed to recognize rules. A Turing machine can check an identifier, but building an airport just to check a ticket would be excessive. Finite automata use fixed memory; a stack handles a class of nesting; linear bounded automata allow more storage, and unrestricted Turing machines go further. In practice, the weakest model that satisfies the requirements should be selected, because the more constrained the model, the more predictable its behavior tends to be.

The next chapter dives into the internals of regular languages: first, we represent a rule as a reliable DFA, then discuss why NFAs are convenient for construction, and how the two models can be converted into one another.