Type 2 Grammar Context-Free Grammar: A Short Note with Formal Meaning and Examples | AI Research

Type 2 Grammar (Context-Free Grammar): A Short Note with Formal Meaning and Examples

Verified Sources

Sep 11, 2026

Chomsky Hierarchy — Type 2 (Context-Free) Grammars

In the Chomsky hierarchy, a Type 2 grammar is a context-free grammar (CFG). Its defining property is that each production rule rewrites one nonterminal independent of the surrounding symbols. Formally, Type 2 grammars have production rules of the form $A \rightarrow \alpha$ , where $A$ is a single nonterminal and $\alpha$ is any string of terminals and/or nonterminals.

This grammar class generates the context-free languages, which are exactly the languages recognizable by a (nondeterministic) pushdown automaton (PDA)—a finite automaton equipped with an unbounded stack.2 A classic example of a Type 2 language is $L=\{a^n b^n \mid n>0\},$ generated by rules such as $S \rightarrow aSb \mid ab$ .

Mermaid intuition (nonterminal rewriting regardless of context):

Key terms: Type-2 grammar context-free grammar context-free language pushdown automaton Chomsky hierarchy

Chomsky hierarchy - Wikipedia - Defines Type-2 rules $A \rightarrow \alpha$ and equivalence to nondeterministic pushdown automata; includes $a^n b^n$ example. ↩ ↩² ↩³
Pushdown Automata • Non-Context-Free Languages (TOC notes PDF) - States the theorem: a language is context-free iff some PDA recognizes it. ↩

Production-rule form (the “context-free” constraint)

A Type 2 grammar is typically specified as a 4-tuple $G=(N,\Sigma,S,P),$ where $N$ is the set of nonterminals, $\Sigma$ is the set of terminals, $S \in N$ is the start symbol, and $P$ is the set of production rules.

For Type 2 (CFGs), each rule must look like: $A \rightarrow \alpha \quad \text{with } A \in N, \ \alpha \in (N\cup\Sigma)^*.$ This means the left-hand side contains exactly one nonterminal, removing any dependence on left/right neighbors—hence “context-free.”

Key terms (again, for recall): start symbol nonterminal terminal production rule derivation

Formal Models of Language: Grammars (PDF, Cambridge notes) - Gives CFG tuple definition and Type 2 production form; discusses CFG structure and hierarchy rule constraints. ↩ ↩²

How a CFG “generates” strings (derivation idea)

1
Step 1
Begin with the start symbol $S$ ; it represents the whole sentence/string category.
2
Step 2
Pick a nonterminal $A$ occurring in the current sentential form and replace it using a rule $A \rightarrow \alpha$ .
3
Step 3
Keep rewriting nonterminals. If a sentential form becomes a string of only terminals, that string is in the language.
4
Step 4
"The language of the grammar is the set of all terminal strings obtainable by some sequence of rule applications."

Example schema (for $a^n b^n$ ):

Use $S \rightarrow aSb$ repeatedly to “nest” one more $a$ and one more $b$

End with $S \rightarrow ab$ to terminate the recursion.

Footnotes

Context-Free Grammars (University of Rochester course page) - Explains the notion of language $L(G)$ generated by derivations from the start symbol. ↩

Chomsky hierarchy - Wikipedia - Defines Type-2 rules $A \rightarrow \alpha$ and equivalence to nondeterministic pushdown automata; includes $a^n b^n$ example. ↩

Canonical examples (and what they illustrate)

1) Well-formed parentheses / balanced nesting (classic Type 2 behavior)

A canonical CFG for balanced parentheses uses recursion: $S \rightarrow (S) \mid SS \mid \\varepsilon.$ This grammar captures nesting and concatenation via recursive structure, which is characteristic of context-free languages.

2) $a^n b^n$ (matching counts via a stack-like structure)

The language $\\{a^n b^n\\mid n>0\\}$ is generated by:

$S \rightarrow aSb$
$S \rightarrow ab$ illustrating how CFG recursion can enforce equal numbers of two symbols.

Why “stack memory” matches CFG structure: PDAs can match nested/paired structures using a stack; therefore context-free languages correspond exactly to what such machines can recognize.2

Key terms: balanced parentheses recursion nesting structure concatenation termination production

Context-free grammar - Wikipedia - Provides canonical CFG examples for balanced parentheses using recursive productions. ↩
Chomsky hierarchy - Wikipedia - Defines Type-2 rules $A \rightarrow \alpha$ and equivalence to nondeterministic pushdown automata; includes $a^n b^n$ example. ↩ ↩²
Pushdown Automata • Non-Context-Free Languages (TOC notes PDF) - States the theorem: a language is context-free iff some PDA recognizes it. ↩

Chomsky hierarchy placement of Type 2

Rule restriction for Type 2 and corresponding recognizer power.

Common points people confuse

Pro Tip: A good 5-line short note template

Write: (1) definition of Type-2 as CFG rules $A \to \alpha$ , (2) mention it’s in Chomsky hierarchy type 2, (3) state it generates context-free languages, (4) state PDA equivalence, (5) give one small example like $a^n b^n$ or balanced parentheses with rules.

Warning: Don’t accidentally describe Type 1 or Type 3

Type 1 (context-sensitive) has more restrictive constraints on length/position of sentential forms, while Type 3 (regular) has far more limited rule shapes; Type 2 is specifically “single nonterminal on the LHS” (context-free).2

Chomsky hierarchy - Wikipedia - Defines Type-2 rules $A \rightarrow \alpha$ and equivalence to nondeterministic pushdown automata; includes $a^n b^n$ example. ↩
Formal Models of Language: Grammars (PDF, Cambridge notes) - Gives CFG tuple definition and Type 2 production form; discusses CFG structure and hierarchy rule constraints. ↩

From grammar rules to language recognition (Type 2)

Type 2 CFG rules

Step A

Rules are of the form $A \rightarrow \alpha$ with single nonterminal LHS."

Derivations

Step B

Start from $S$ and repeatedly rewrite nonterminals until only terminals remain."

Generated strings = language

Step C

All terminal strings derivable by some sequence form the context-free language."

Computational view

Step D

Exactly the same class is recognizable by a nondeterministic PDA with a stack."

Knowledge Check

Question 1 of 4

Q1Single choice

In a Type 2 (context-free) grammar, a production rule has what required form?

A → α where A is a single nonterminal

αAβ → αγβ where length never decreases

A → a or A → aB only (at most one terminal per rule)

Any rule of the form α → β without restrictions

Explore Related Topics

Ambiguity in Context-Free Grammars, Disambiguation Techniques, and Analysis of the Grammar $S \rightarrow aS/Sa/a$

Variable Inductance and Capacitance Transducers

Short Notes on Cook's Theorem, Randomized Algorithms, and Bin Packing

The notes cover Cook’s theorem establishing SAT as NP‑complete, the design and analysis of randomized (Las Vegas and Monte Carlo) algorithms, and the NP‑hard bin‑packing problem with its common heuristics and approximation guarantees.

Cook’s theorem shows every language $L\in\mathrm{NP}$ reduces to SAT via a polynomial‑time function $f$ such that $x\in L\iff f(x)\in\mathrm{SAT}$ , making SAT the first NP‑complete problem.
Randomized algorithms: Las Vegas algorithms are always correct with expected runtime (e.g., $\mathbb{E}[T(n)]=O(n\log n)$ for randomized quicksort); Monte Carlo algorithms run in fixed time with error ≤½, which can be reduced by amplification to $(\tfrac12)^k$ after $k$ repetitions.
Bin packing: the decision version is NP‑complete and the optimization version NP‑hard; heuristics like First Fit Decreasing guarantee $\mathrm{FFD}(I)\le\frac{11}{9}\mathrm{OPT}(I)+\frac{6}{9}$ .
Together they illustrate three core CS themes: proving hardness via reductions, leveraging randomness for efficient algorithm design, and using heuristics/approximation to tackle intractable optimization problems.

Browse all research articles

Type 2 Grammar (Context-Free Grammar): A Short Note with Formal Meaning and Examples

Chomsky Hierarchy — Type 2 (Context-Free) Grammars

Footnotes

Production-rule form (the “context-free” constraint)

Footnotes

How a CFG “generates” strings (derivation idea)

Footnotes

Canonical examples (and what they illustrate)

1) Well-formed parentheses / balanced nesting (classic Type 2 behavior)

2) anbna^n b^nanbn (matching counts via a stack-like structure)

Footnotes

Chomsky hierarchy placement of Type 2

Common points people confuse

Pro Tip: A good 5-line short note template

Warning: Don’t accidentally describe Type 1 or Type 3

Footnotes

From grammar rules to language recognition (Type 2)

Type 2 CFG rules

Derivations

Generated strings = language

Computational view

Knowledge Check

Explore Related Topics

2) $a^n b^n$ (matching counts via a stack-like structure)