Unit 2: Context-free languages
Theory of Computation notes · PTU syllabus (PGCA1927)
On this page
Unit summary
Context-free grammars describe nested structures such as programming-language syntax. This unit covers the properties of context-free languages, the Chomsky classification, context-free grammars, simplification of grammars, Chomsky normal form and Greibach normal form.
After this unit you can
- Classify grammars using the Chomsky hierarchy
- Write context-free grammars and derivations
- Simplify grammars
- Convert grammars to Chomsky and Greibach normal forms
PTU syllabus topics
- Properties of context-free languages
- Chomsky classification
- context-free grammars
- grammar simplification
- Chomsky Normal Form
- Greibach Normal Form
- Type 0: recursively enumerable
Turing machine
- Type 1: context-sensitive
Linear bounded automaton
- Type 2: context-free
Pushdown automaton
- Type 3: regular
Finite automaton
Topic 1
Chomsky classification of grammars
- Type 3: regular grammars
A → aB or A → a; recognised by finite automata
- Type 2: context-free grammars
A → α (one variable on the left); pushdown automata
- Type 1: context-sensitive grammars
αAβ → αγβ, length non-decreasing; linear bounded automata
- Type 0: unrestricted grammars
α → β; Turing machines
- Each class contains the ones above it in the list of restrictions: regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable.
Topic 2
Context-free grammars
- A CFG is a 4-tuple (V, T, P, S): variables, terminals, productions of the form A → α, and the start symbol.
Example
Balanced parentheses: S → (S) S or S → ε. Palindromes over {a, b}: S → aSa, bSb, a, b or ε. {aⁿbⁿ}: S → aSb or ε.
- Derivations: leftmost (expand the leftmost variable first) and rightmost; a parse tree shows the structure. Expression grammar: E → E + T or T; T → T × F or F; F → (E) or id.
Topic 3
Properties of context-free languages
Union, concatenation, Kleene star
Yes
Combine grammars with a new start symbol
Intersection
No
{aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, not context-free
Complement
No
Follows from non-closure under intersection
Intersection with a regular language
Yes
Product of PDA and DFA
- Pumping lemma for CFLs: long strings can be written uvwxy with v and x pumped together; proves {aⁿbⁿcⁿ} is not context-free. Decidable: emptiness, finiteness and membership (CYK algorithm).
Topic 4
Simplification of grammars
- 1Remove ε-productions (except S → ε if needed)
- 2Remove unit productions (A → B)
- 3Remove useless symbols — first non-generating, then unreachable
Example
S → AB or a; A → a; B → C; C → b; D → d. Unit removal: B → b, C → b. D is unreachable and C becomes unreachable, so the result is S → AB or a, A → a, B → b.
Topic 5
Chomsky normal form
- CNF: every production is A → BC or A → a (plus S → ε if ε is in the language). Every CFG without ε can be converted; parse trees become binary, which the CYK algorithm uses.
- 1Simplify the grammar
- 2Replace terminals in long right sides by new variables (Xa → a)
- 3Break right sides longer than two into chains of new variables
Example
S → aSb or ab becomes S → XaY or XaXb; Y → SXb; Xa → a; Xb → b.
Topic 6
Greibach normal form
- GNF: every production is A → aα, where a is a terminal and α is a (possibly empty) string of variables. Each derivation step generates one terminal, so a string of length n needs exactly n steps — useful for constructing PDAs and parsers.
- Conversion: start from CNF, order the variables, substitute to make productions begin with a higher-numbered variable or terminal, and remove left recursion (A → Aα or β becomes A → β or βZ; Z → α or αZ).
Key terms
- Context-free grammar
- Grammar with a single variable on the left of each production
- Derivation
- Sequence of production applications
- Parse tree
- Tree showing how a string is derived
- Chomsky normal form
- Productions A → BC or A → a
- Greibach normal form
- Productions starting with a terminal followed by variables
Quick revision
- Type 0 to 3 grammars and their machines.
- CFG 4-tuple; examples; leftmost and rightmost derivations; parse trees.
- Closure: union, concatenation, star yes; intersection, complement no; CFL pumping lemma.
- Remove ε, unit and useless productions.
- CNF conversion; GNF and left-recursion removal.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State the four types of the Chomsky hierarchy.
- Q2.Write a CFG for {aⁿbⁿ : n ≥ 1}.
- Q3.Are CFLs closed under intersection?
- Q4.What is a unit production?
- Q5.Define Chomsky normal form.
- Q6.Why is GNF useful?
Long-answer questions
- Q1.Explain the Chomsky classification of grammars.
- Q2.Explain context-free grammars with derivations and parse trees.
- Q3.Simplify a given context-free grammar.
- Q4.Convert a grammar to CNF and GNF.
Stuck on this unit?
Message SBS on WhatsApp for help with Theory of Computation, or to ask about studying M.Sc IT at Synetic.