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

The first rule at the stone gate only requires checking the first and last characters, finite state machines are sufficient. The second gate demands arbitrary-depth parentheses matching, requiring the guard to carry a stack. Beyond that, rules might need to rewrite content at any position on the work tape. The Chomsky hierarchy organizes these "how much computational power is required" into four distinct levels.

Learning Objectives

• Accurately identify the four classes of grammars and their corresponding parsing 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$ denote a non-terminal symbol and $\Sigma$ denote a terminal symbol. 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$	Pushdown automaton	Nested parentheses, expression syntax
1: Context-sensitive grammar	Rules generally do not shorten strings; special cases must handle empty-string productions (ε-rules)	Linear bounded automaton	${a^nb^nc^n \mid n \geq 1}$
0: Unrestricted grammar	Left side must contain at least one non-terminal; otherwise, no restrictions apply	Turing machine	Recursively enumerable languages

Different textbooks provide equivalent but slightly varying definitions of type 1 grammars, especially regarding ε-productions. Before applying any theorem, it is essential to verify which definition and exception conditions are being used.

Language classes form a strict containment hierarchy:

$$ \text{Regular} \subsetneq \text{Context-Free} \subsetneq \text{Context-Sensitive} \subsetneq \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^nb^n\mid n\ge0} $$

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| \geq p$ can be divided into $w = xyz$ satisfying:

1. $|xy| \leq p$;
2. $|y| > 0$;
3. For all $i \geq 0$, $xy^iz \in L$.

For the string $a^pb^p$, since the first $p$ characters are all a, the substring $y$ must consist only of a. Repeating or removing $y$ 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.

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 mechanism enables the processing of arbitrarily deep balanced parentheses.

"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^nb^nc^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	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 (CFGs), SSA, lattices and fixed-point algorithms
Code generation	IR and target information	Instruction selection, scheduling, register allocation

The theoretical hierarchy helps us understand expression boundaries, 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;
• 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. 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 its infinite-depth counterpart 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 computational requirements of a lineage rule are not about assigning a hierarchy or ranking to tools. Finite state machines handle fixed memory, stacks manage a class of recursive nesting, and linear bounded storage extends the capabilities of Turing machines. 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.