Chomsky hierarchy and applications of CFGs
Chomsky hierarchy classifies grammars and languages (Type-0 to Type-3) and shows where context-free grammars (CFGs) sit and how CFGs are used (parsing, compilers, PDAs).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two sentences: The Chomsky hierarchy gives a precise classification of language families used in programming language design, compilers, and formal verification. Context-free grammars (CFGs, Type-2) are especially important because they describe programming-language syntax and can be parsed by efficient algorithms and implemented with pushdown automata (PDAs).
Key ideas
Start from first principles and define terms in plain English.
- Alphabet: a finite non-empty set of symbols, usually written Σ. Example: Σ = {a, b}.
- String: a finite sequence of symbols from an alphabet. The empty string is written ε.
- Language: a set of strings over an alphabet.
- Grammar: a 4-tuple G = (V, Σ, P, S) where V is a finite set of symbols called nonterminals, Σ is a finite set of terminals (Σ ∩ V = ∅), S ∈ V is the start symbol, and P is a finite set of productions (rules) of the form α → β where α and β are strings from (V ∪ Σ)* with some restrictions depending on grammar type.
- Derivation: applying production rules starting from S to obtain strings of terminals; written S ⇒* w means w (in Σ*) is derivable.
Chomsky hierarchy (exact definitions used in exams). Bold each type and give its formal production form and intuitive meaning.
Type-0 (Recursively enumerable / Unrestricted grammars): Productions are of the form α → β where α ∈ (V ∪ Σ)* V (V ∪ Σ)* (i.e., α must contain at least one nonterminal) and β ∈ (V ∪ Σ)*. These generate exactly the recursively enumerable languages (languages accepted by Turing machines). No other restrictions.
Type-1 (Context-sensitive grammars, CSG): Productions are of the form αAβ → αγβ where A ∈ V, α, β ∈ (V ∪ Σ)* (the context) and γ ∈ (V ∪ Σ)+ (γ is non-empty). Equivalently, every production increases or preserves string length: |β| ≥ |α| for each production α → β, except possibly allowing the start symbol S → ε only if S does not appear on RHS elsewhere. These generate context-sensitive languages (accepted by linear bounded automata).
Type-2 (Context-free grammars, CFG): Productions are of the form A → γ where A ∈ V and γ ∈ (V ∪ Σ)*. No context is required. These generate context-free languages (CFLs). Important: many programming language grammars are context-free or close to it.
Type-3 (Regular grammars): Productions are restricted to either A → aB or A → a (right-linear) or A → Ba or A → a (left-linear), where A,B ∈ V and a ∈ Σ; possibly allow S → ε. These generate regular languages, equivalent to finite automata and regular expressions.
Inclusion relation (what to draw): Draw a nested Venn-like diagram with Type-3 inside Type-2 inside Type-1 inside Type-0. Label each region with the type and an example language: Type-3 example: {a}*, Type-2 but not 3: {a^n b^n | n ≥ 0}, Type-1 but not 2: {a^n b^n c^n | n ≥ 0}, Type-0: any recursively enumerable non-context-sensitive language.
Theorem (Equivalence CFG ↔ PDA) — exact statement used in exams:
- Theorem: A language L is context-free iff there exists a nondeterministic pushdown automaton (PDA) that accepts L (by final state or empty stack; both acceptance modes are equivalent for languages). Assumptions: PDAs are allowed nondeterminism and a single stack.
Sketch proof steps (what examiners expect):
- From CFG to PDA: Construct a PDA that simulates leftmost derivations. Start by pushing S on stack. On stack top nonterminal A, nondeterministically choose a production A → γ and replace A by γ on the stack. On terminal a at both input head and stack top, pop stack and advance input. Accept when stack empty and input exhausted. Draw transition rules: δ(q, ε, A) contains (q, γ) for each A → γ; δ(q, a, a) contains (q, ε).
- From PDA to CFG: Create nonterminals [pAq] representing the language of strings that cause the PDA to go from state p with A on stack to state q with that portion of stack consumed. For each PDA move, write productions that reflect stack behaviour. This construction is longer; provide the standard construction and explain it builds a CFG generating exactly strings that the PDA accepts.
Normal forms (definitions and why used):
- Chomsky Normal Form (CNF): Every production is either A → BC (B,C ∈ V) or A → a (a ∈ Σ). Optionally S → ε if ε ∈ L(G) and S does not appear on the right-hand side of any production. CNF is used in many proofs and in the CYK parsing algorithm.
- Greibach Normal Form (GNF): Every production is of the form A → aα where a ∈ Σ and α ∈ V* (possibly empty). GNF is useful to show that every CFL is generated by a grammar that produces a terminal first — helps construct PDAs that read input left-to-right.
Applications of CFGs (short, plain):
- Syntax of programming languages and expression grammars (parsers use CFGs). Mention parsing algorithms: LL, LR families (refer to Deterministic and nondeterministic PDA and parser theory topics) and CYK for CNF grammars.
- Program analyzers, code generation, and some natural language fragments.
Formulas
(For a programming/formal-language topic, list syntax to remember.)
Grammar G = (V, Σ, P, S) — V = nonterminals, Σ = terminals, P = productions, S = start symbol. (SI unit: none; applies always)
Production: A -> α — A in V, α in (V ∪ Σ). (unit: none; for CFGs; for other grammar types, see the type-specific forms above)
CNF productions: A -> B C or A -> a — B,C in V, a in Σ; S -> ε allowed only if ε in L(G). (unit: none)
GNF production: A -> a α — a in Σ, α in V. (unit: none)
PDA transition form: δ(q, a, X) -> (p, γ) — reading input a (or ε), with stack top X, move to state p and replace X by γ (γ ∈ Γ*, stack alphabet). (unit: none)
Worked examples
Example 1 — Classify grammars (typical exam question) Given G1 with productions: S -> aS | a. Classify. Steps and answer:
- Productions are S -> aS (A -> aB form) and S -> a (A -> a). These are right-linear: fits Type-3 (regular). So G1 is Type-3 (regular grammar). Provide minimal DFA suggestion: draw states illustrating accepting after reading a.
Example 2 — Convert to CNF (step-by-step) — standard exam exercise Given grammar G: S -> ASA | aB, A -> B | S, B -> b | ε. Steps (show the standard algorithm):
- Add new start symbol S0 -> S.
- Remove ε-productions: find nullable nonterminals (B is nullable; also check consequences), add productions replacing B by ε where it appears.
- Remove unit-productions: replace A -> B and A -> S by A -> (B's RHS) and so on.
- Remove terminals from long productions by introducing new nonterminals for terminals: e.g., X_a -> a.
- Break RHS length > 2 into binary productions by introducing new nonterminals: replace A -> B C D by A -> B X1, X1 -> C D. Final answer: write the CNF grammar (list productions). (Due to length, show the exact intermediate productions in an exam; here we summarized steps — verify exact final set.) Final CNF (one valid result): introduce S0 and auxiliaries X_a, X_SA with rules: S0 -> A X_SA | S A | A S | X_a B | a S -> A X_SA | S A | A S | X_a B | a A -> A X_SA | S A | A S | X_a B | a | b B -> b X_a -> a X_SA -> S A (All RHS are either two nonterminals or a single terminal; ε is not generated, matching the original language.)
Example 3 — Show L = {a^n b^n | n ≥ 0} is context-free and not regular (common short-answer proof)
- Write CFG: S -> a S b | ε. This generates a^n b^n. (Explain derivation: each S -> a S b adds one a on left and one b on right.)
- Prove not regular: either use the pumping lemma for regular languages (briefly mention) or show Myhill–Nerode equivalence classes are infinite. For exams, a short pumping-lemma proof: assume regular, pick pumping length p, choose s = a^p b^p, split s = xyz with |xy| ≤ p and |y| > 0 so y is all a's; pumping i=0 yields fewer a's than b's, contradiction.
Common mistakes
- When classifying grammars, checking only one production instead of all productions (every production must satisfy the type restriction).
- In CFG→PDA construction: not handling terminals correctly (you must match terminal on input and stack top to consume input).
- Mistakenly claiming CFLs are closed under intersection (they are not in general; they are closed under intersection with regular languages).
For your exam
Question types you will see: definitions (state Chomsky types exactly), short notes (applications, normal forms), derivations (derive a string using given grammar), conversions (grammar to CNF or GNF), proofs (show language is or is not regular / context-free), constructions (build PDA for a CFG or CFG for a PDA), parsing trace (CYK table for a given string and CNF grammar). What full-marks answers include:
- Precise definitions (use the form restrictions shown above), clear step-by-step algorithms (e.g., CNF conversion steps), and full derivation traces where asked. For construction proofs (CFG↔PDA), include transition rules or grammar constructions clearly and argue correctness (soundness and completeness). Also know closure properties of CFLs: closed under union, concatenation, Kleene star, homomorphism, inverse homomorphism, substitution, and intersection with regular languages; not closed under intersection, complement, or difference.
Quick check
- What is the production form required for a Type-2 grammar?
- Give a CFG for L = {a^n b^n | n ≥ 0}.
- Are context-free languages closed under complement? Answers: 1. A -> γ where A is a single nonterminal and γ ∈ (V ∪ Σ)*. 2. S -> a S b | ε. 3. No (CFLs are not closed under complement in general).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?