Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

  1. 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, ε).
  2. 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:

  1. 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):

  1. Add new start symbol S0 -> S.
  2. Remove ε-productions: find nullable nonterminals (B is nullable; also check consequences), add productions replacing B by ε where it appears.
  3. Remove unit-productions: replace A -> B and A -> S by A -> (B's RHS) and so on.
  4. Remove terminals from long productions by introducing new nonterminals for terminals: e.g., X_a -> a.
  5. 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)

  1. 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.)
  2. 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

  1. What is the production form required for a Type-2 grammar?
  2. Give a CFG for L = {a^n b^n | n ≥ 0}.
  3. 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?