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

Closure Properties of Context-Free Languages (CFLs)

Alphabet, Language, Grammar, and Derivation: Definitions and Relationships in Formal Language Theory

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

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)