REFERENCE SHEET

Context-free grammars & parsing

A stack adds unbounded nesting to finite-state control.

Before this Finite automata & regular languages

S → (S)S | ε

Definitions

Context-free grammar

A finite collection of productions A→α, where A is one nonterminal and α is a string of terminals and nonterminals, with a designated start symbol.

Derivation and parse tree

A derivation applies productions to generate a terminal string. A parse tree records the hierarchical production structure.

Ambiguity

A grammar is ambiguous if some terminal string has two distinct parse trees. This is a property of a grammar; some languages have no unambiguous context-free grammar.

Key theorems

Pushdown equivalence

A language is context-free exactly when a nondeterministic pushdown automaton recognizes it. Deterministic pushdown automata recognize a strictly smaller class.

Closure qualifications

Context-free languages are closed under union, concatenation, star, and intersection with a regular language, but not in general under intersection or complement.

CYK membership

For a grammar in Chomsky normal form and a nonempty length-n input, CYK decides membership in O(|P|n³) time, where P is the production set. Treat ε separately.

Notable applications

Parsing

Grammars describe nested expressions and syntactic structure in compilers.

Structured documents

Balanced delimiters and recursive tree-shaped formats require more memory than a finite automaton in general.

Work it out

Try before revealing

01 / Derive

Using S→(S)S | ε, derive ()().

Hint

Expand the trailing S once more.

Solution

S⇒(S)S⇒()S⇒()(S)S⇒()()S⇒()().

02 / Explain

Why is E→E+E | E*E | id ambiguous?