Context-Free Languages and Pushdown Automata

Context-free grammars generate languages with nested, recursive structure, and pushdown automata recognize exactly these languages by augmenting a finite control with an unbounded stack.

Definition

A context-free language is generated by a grammar whose rules rewrite a single nonterminal symbol independently of context, and it is recognized by a pushdown automaton, a finite automaton equipped with a stack that provides last-in, first-out memory of unbounded depth.

Scope

This topic covers context-free grammars and derivations, parse trees and ambiguity, the equivalence of context-free grammars with pushdown automata, normal forms such as Chomsky normal form, the pumping lemma for context-free languages, and the closure and decision properties that distinguish this class from the regular languages.

Core questions

• What kinds of nested or recursive patterns require a stack rather than finite memory?
• Why are context-free grammars and pushdown automata equivalent in power?
• When is a grammar ambiguous, and why does ambiguity matter for parsing?
• Which decision problems for context-free languages are solvable, and which are not?

Key theories

Grammar–automaton equivalence

A language is context-free if and only if it is accepted by some pushdown automaton, so the generative grammar view and the stack-machine view describe the same class of languages.

Chomsky normal form

Every context-free grammar can be rewritten so that each rule produces either two nonterminals or a single terminal, a normal form that underlies parsing algorithms and inductive proofs about the class.

Pumping lemma for context-free languages

Every sufficiently long string in a context-free language can be split so that two of its parts are pumped together, a property that fails for languages requiring more than stack memory and so proves them non-context-free.

Clinical relevance

Context-free grammars specify the syntax of nearly every programming language and many data formats, and pushdown-style parsing algorithms turn these grammars into the syntactic analyzers at the heart of compilers and interpreters, making this topic the theoretical foundation of programming-language processing.

History

Chomsky introduced context-free grammars in the late 1950s as part of his hierarchy, and they were independently used by Backus and Naur to define the syntax of the ALGOL programming language. The equivalence with pushdown automata and the structural theory of the class were worked out through the 1960s.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Why does parsing a programming language need a stack?

Programs contain nested constructs such as parentheses, blocks, and function calls whose matching depth is unbounded. A stack records each unfinished construct and pops it when closed, which is exactly the memory discipline a pushdown automaton provides and a finite automaton lacks.

What does it mean for a grammar to be ambiguous?

A grammar is ambiguous when some string has more than one parse tree, meaning it can be derived with genuinely different structures. Ambiguity is undesirable for programming languages because it leaves the meaning of code unclear, so language designers seek unambiguous grammars or add disambiguation rules.