Self-checkedTier 1 10 min readtoc.context-free-grammars

Context-free grammars and derivations

Context-free grammars as generators of languages: variables, terminals, productions, derivations (leftmost, rightmost, in any order), sentential forms, parse trees and their relation to derivations, the language of a grammar, designing grammars for the standard GATE languages (a^n b^n, palindromes, balanced parentheses, equal counts, i = j or j = k), regular languages as a special case, and the usual wrong grammars.

Why it exists

Regular expressions cannot count or match nested structure: $a^n b^n$ , balanced parentheses and palindromes are beyond finite automata. A context-free grammar (CFG) is the notation for exactly this: rewriting rules where a single variable is replaced regardless of its neighbours (the "context-free" part). Grammars describe the syntax of programming languages (the compiler side of this site) and, in theory, the languages accepted by pushdown automata. GATE asks: write a grammar for a language, say which language a grammar generates, count derivations or strings, and compare grammars.

Prerequisites

Alphabets, strings and languages

You need strings, concatenation and languages as sets of strings (alphabets, strings and languages).

Precise definitions

A context-free grammar is a 4-tuple $G = (V, \Sigma, R, S)$ :

$V$ : a finite set of variables (nonterminals);
$\Sigma$ : a finite set of terminals, disjoint from $V$ ;
$R$ : a finite set of productions $A \to \alpha$ with $A \in V$ and $\alpha \in (V \cup \Sigma)^*$ (the right side may be empty, written $\varepsilon$ );
$S \in V$ : the start variable.

Several productions with the same left side are written together: $A \to \alpha \mid \beta$ .

Derivation step. $u A v \Rightarrow u \alpha v$ if $A \to \alpha$ is a production. $\Rightarrow^*$ means zero or more steps. A string in $(V \cup \Sigma)^*$ derivable from $S$ is a sentential form; one that contains only terminals is a sentence. The language of $G$ is

$L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}.$

A language is context-free (a CFL) if it is $L(G)$ for some CFG $G$ .

Leftmost and rightmost derivations. In a leftmost derivation the variable replaced in every step is the leftmost variable of the sentential form; in a rightmost derivation it is the rightmost.

Parse tree. A rooted ordered tree: the root is labelled $S$ , every internal node is labelled by a variable $A$ and its children (in order) spell the right side of a production $A \to X_1 \cdots X_k$ (a single child $\varepsilon$ for an empty right side), and the leaves are terminals (or $\varepsilon$ ). The yield is the string of the leaves read from left to right; $w \in L(G)$ exactly when some parse tree has yield $w$ .

How it works

Derivations and parse trees

A parse tree remembers which production was applied to which variable but not the order in which the variables were expanded. Different orders give different derivations of the same tree. Each parse tree has exactly one leftmost derivation and one rightmost derivation, so counting parse trees equals counting leftmost derivations equals counting rightmost derivations (checked by exhaustive search on 120 random grammars).

Example: $G$ with $S \to A B$ , $A \to aA \mid a$ , $B \to bB \mid b$ generates $a^+ b^+$ . The string $aabbb$ has one parse tree. Its leftmost derivation expands $A$ 's before $B$ 's:

Leftmost derivation of aabbb: start

Parser run by a script, not typed

Leftmost derivation (the sentential form is on the left; the string to derive is on the right).

1S → A B
2A → a A
3A → a
4B → b B
5B → b

sentential form

string to derive

aabbb

action start

parse tree so far

Step 0

Start from S. A leftmost derivation always replaces the leftmost nonterminal of the sentential form; each step expands one node of the parse tree.

0 / 6

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc3-traces.py

and its rightmost derivation expands the $B$ 's first:

Rightmost derivation of aabbb: start

Parser run by a script, not typed

Rightmost derivation (the sentential form is on the left; the string to derive is on the right).

1S → A B
2A → a A
3A → a
4B → b B
5B → b

sentential form

string to derive

aabbb

action start

parse tree so far

Step 0

Start from S. A rightmost derivation always replaces the rightmost nonterminal of the sentential form; each step expands one node of the parse tree.

0 / 6

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc3-traces.py

Both are the same tree. Derivations in other orders also exist: the derivation has $1 + 2 + 3 = 6$ steps, the $A$ chain (2 steps) and the $B$ chain (3 steps) can be interleaved in $\binom{5}{2} = 10$ ways, so $aabbb$ has 10 derivations but a single parse tree (found by exhaustive search).

With empty right sides the tree has $\varepsilon$ leaves. For balanced parentheses, $S \to (\,S\,)\,S \mid \varepsilon$ :

Leftmost derivation of (()()): start

Parser run by a script, not typed

Leftmost derivation (the sentential form is on the left; the string to derive is on the right).

1S → ( S ) S
2S → ε

sentential form

string to derive

(()())

action start

parse tree so far

Step 0

Start from S. A leftmost derivation always replaces the leftmost nonterminal of the sentential form; each step expands one node of the parse tree.

0 / 7

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc3-traces.py

Designing grammars

Ways to think about a language:

Matching pairs (outside in): $S \to a S b \mid \varepsilon$ generates $a^n b^n$ ; $S \to a S b b \mid \varepsilon$ generates $a^n b^{2n}$ .
Concatenation of independent parts: $S \to A B$ with $A \to a A \mid \varepsilon$ , $B \to b B \mid \varepsilon$ generates $a^* b^*$ .
Union: $S \to S_1 \mid S_2$ . For $\{a^i b^j c^k : i = j \text{ or } j = k\}$ write $S \to X C \mid A Y$ with $X \to a X b \mid \varepsilon$ , $C \to c C \mid \varepsilon$ , $A \to a A \mid \varepsilon$ , $Y \to b Y c \mid \varepsilon$ .
Unequal counts by splitting into cases: $i \ne j$ means $i > j$ or $i < j$ : $S \to a S b \mid A \mid B$ , $A \to aA \mid a$ , $B \to bB \mid b$ (peel matched pairs, then at least one unmatched symbol on one side).
Reversal / palindromes: $S \to a S a \mid b S b \mid a \mid b \mid \varepsilon$ (the middle is $\varepsilon$ or one symbol); only even palindromes: drop $a \mid b$ .
Nesting: $S \to (\,S\,)\,S \mid \varepsilon$ for balanced parentheses (a balanced string is empty or a balanced string inside a pair followed by a balanced string).
Equal numbers of $a$ and $b$ in any order: $S \to a S b S \mid b S a S \mid \varepsilon$ . (It is correct but ambiguous; see the next page for an unambiguous grammar.)

Grammars for the standard languages: start

Computed by a script, not typed

language	grammar	strings of length at most 10
a^n b^n
a^n b^(2n)
even palindromes w w^R
all palindromes
balanced parentheses
equal numbers of a and b
a^i b^j with i ≥ j
a^i b^j with i ≠ j
a^i b^j c^k with i = j or j = k

Step 0

Each grammar was compared with a direct description of its language on every string up to length 10 over its alphabet.

0 / 9

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc3-traces.py

How fast the languages grow differs a lot:

How many strings of each length a grammar generates: start

Computed by a script, not typed

length	a^n b^n	even palindromes	all palindromes	balanced parentheses	equal a and b
length 0
length 1
length 2
length 3
length 4
length 5
length 6
length 7
length 8
length 9
length 10

Step 0

Each column is the language of one grammar: its strings up to length 10 are generated by iterating the productions until nothing new appears. The columns grow in very different ways: a^n b^n has one string for every even length, balanced parentheses the Catalan numbers, equal a and b the central binomial coefficients.

0 / 11

computed by script: the machine is simulated or the sets are constructed by scripts/toc_lib.py, one step at a time. python3 scripts/gen-toc3-traces.py

Regular languages are context-free

Every regular language has a right-linear grammar: one variable $A_q$ per DFA state, a production $A_q \to a A_{\delta(q, a)}$ for every transition and $A_q \to \varepsilon$ for every accepting state. For the DFA of "ends with $01$ " this grammar generates the language and gives every string exactly one parse tree (checked on all strings up to length $10$ ). So regular languages $\subsetneq$ CFLs ( $a^n b^n$ is context-free and not regular).

Membership

Deciding whether $w \in L(G)$ is possible for every grammar: the CYK algorithm decides it in cubic time after the grammar is put in Chomsky normal form (normal forms). With $\varepsilon$ -productions a sentential form can be longer than the string it finally produces, which is why normal forms first remove them.

Worked examples

EX 1Which language

Easy

$S \to a S b \mid ab$ generates $\{a^n b^n : n \ge 1\}$ (the version with $\varepsilon$ generates $n \ge 0$ ). $S \to S S \mid a$ generates $a^+$ . $S \to a S \mid b S \mid \varepsilon$ generates all strings over $\{a, b\}$ . $S \to 0 S 1 \mid \varepsilon$ generates $\{0^n 1^n\}$ .

EX 2A leftmost derivation

Easy

With $S \to aSb \mid \varepsilon$ , the string $aabb$ : $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$ (the last step uses $S \to \varepsilon$ ). Three steps; a string $a^n b^n$ takes $n + 1$ steps.

EX 3Write a grammar for i greater than or equal to j

Medium

$\{a^i b^j : i \ge j\}$ : first $S \to a S b \mid a S \mid \varepsilon$ is correct but ambiguous. A cleaner grammar: $S \to a S \mid T$ , $T \to a T b \mid \varepsilon$ ( $i - j$ extra $a$ 's first, then matched pairs). Both were compared with the language on all strings up to length $10$ ; the second gives every string exactly one parse tree.

EX 4A wrong grammar

Medium

A common answer for "equal numbers of $a$ and $b$ " is $S \to a S b \mid S S \mid \varepsilon$ . It generates only strings in which every prefix has at least as many $a$ 's as $b$ 's (the balanced strings with $a$ as "(" and $b$ as ")"); $ba$ has equal counts but is not generated. A correct grammar is $S \to a S b S \mid b S a S \mid \varepsilon$ .

EX 5Typical questions

GATE level

(a) How many strings of length $6$ does $S \to a S b \mid \varepsilon$ generate? $1$ ( $a^3 b^3$ ). (b) How many strings of length $10$ does $S \to (\,S\,)\,S \mid \varepsilon$ generate? $42$ , the fifth Catalan number (counted by program). (c) Is $\{a^n b^n c^n\}$ context-free? No (pumping lemma for CFLs, later). (d) How many derivations does a string have? Many; one leftmost, one rightmost per parse tree. (e) Which of these generates palindromes? The grammar must produce both outer symbols together and allow an empty middle or a single symbol; $S \to aSa \mid bSb \mid \varepsilon$ misses the odd ones.

Cheat box

$G = (V, \Sigma, R, S)$ ; $L(G) = \{w \in \Sigma^* : S \Rightarrow^* w\}$ ; left side is a single variable.
Parse tree $\leftrightarrow$ one leftmost derivation $\leftrightarrow$ one rightmost derivation; many other orders.
$a^n b^n$ : $S \to aSb \mid \varepsilon$ . Palindromes: $S \to aSa \mid bSb \mid a \mid b \mid \varepsilon$ . Balanced: $S \to (S)S \mid \varepsilon$ . Equal counts: $S \to aSbS \mid bSaS \mid \varepsilon$ .
Unions: $S \to S_1 \mid S_2$ . Concatenation: $S \to S_1 S_2$ . Star: $S \to S_1 S \mid \varepsilon$ .
Regular $\subset$ context-free (right-linear grammars).

Traps and GATE patterns

Connections

Builds on

Alphabets, strings and languages

Unlocks

Ambiguity, left recursion and left factoringPrerequisite of Ambiguity, left recursion and left factoringuses Alphabets, strings and languagesimplemented by Ambiguity in grammarsPrerequisite of Ambiguity in grammarsuses Simplification, CNF and GNFPrerequisite of Simplification, CNF and GNFuses Pushdown automatacontrasts with PDA and CFG equivalencePrerequisite of PDA and CFG equivalenceuses

Across subjects

Ambiguity, left recursion and left factoringanalogous-to

Within this subject

Alphabets, strings and languagesuses Ambiguity in grammarsimplemented-by Simplification, CNF and GNFimplemented-by Pushdown automataimplemented-by

Ambiguity is the next question about a grammar (ambiguity); normal forms and the CYK algorithm are the next tools (normal forms); the machine that accepts exactly the CFLs is the pushdown automaton (PDA); compilers use grammars of the same kind for syntax (grammar ambiguity in compilers).

PYQs

17 previous year questions from your book. I re-solved each one myself (16 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2017 · Set 1 · MCQQ32 · page 201 of the book

If G is a grammar with productions S → SaS | aSb | bSa |
SS | ε where S is the start variable, then which one of the
following strings is not generated by G?

(a)abab
(b)aaab
(c)abbaa
(d)babba

GATE 2016 · Set 1 · MCQ · 1 markQ34 · page 201 of the book

Which of the following languages is generated by the given
grammar?
S→ aS|bS|ε

(a){anbm | n, m >= 0}
(b){w ε {a,b}*| w has equal number of a's and b's}
(c){an | n >= 0} U {bn | n >= 0} U {anbn | n >= 0}
(d){a,b}*

GATE 2025 · Set 2 · MCQ · 1 markQ6 · page 225 of the book

Consider the following context-free grammar G, where S,
A, and B are the variables (non-terminals), a and b are the
terminal symbols, S is the start variable, and the rules of
G are described as:
S → aaB | Abb
A → a | aA
B → b | bB
Which ONE of the languages L(G) is accepted by G?

(a)L(G) = {a2bn | n ≥ 1} ∪ {anb2 | n ≥ 1}
(b)L(G) = {anb2n | n ≥ 1} ∪ {a2nbn | n ≥ 1}
(c)L(G) = {anbn | n ≥ 1}
(d)L(G) = {a2nb2n | n ≥ 1}

GATE 2024 · Set 2 · MSQ · 1 markQ8 · page 226 of the book

Consider a context-free grammar G with the following
3 rules.
S → aS, S → aSbS, S → c
Let w ∈ L(G). Let na (w), nb (w), nc (w) denote the
number of times a, b, c occur in w, respectively.
Which of the following statements is/are TRUE?

(a)na(w) > nb(w)
(b)na(w) > nc (w) - 2
(c)nc(w) = nb(w) + 1
(d)nc(w) = nb(w) * 2

GATE 2023 · MCQ · 2 marksQ12 · page 226 of the book

Consider the context-free grammar G below
S → aSb | X
X → aX | Xb | a | b ,
where S and X are non-terminals, and a and b are
terminal symbols. The starting non-terminal is S.
Which one of the following statements is CORRECT?

(a)The language generated by G is (a + b)*
(b)The language generated by G is a*(a + b)b*
(c)The language generated by G is a*b*(a + b)
(d)The language generated by G is not a regular language THEORY OF COMPUTATION

GATE 2017 · Set 1 · MCQ · 1 markQ20 · page 227 of the book

Consider the following context-free grammar over the
alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT | abcT
T → bT | b

Which one of the following represents the language
generated by the above grammar?

(a){(ab)n (cb)n | n >= 1}
(b){(ab) n cb (m1) cb (m2) ....... cb(mn) |n, m1 , m2 ,....., mn >= 1}
(c){(ab)n (cbm)n | m, n >= 1}
(d){(ab)n (cbn)m | m, n >= 1} THEORY OF COMPUTATION

GATE 2017 · Set 2 · MCQ · 2 marksQ22 · page 228 of the book

Identify the language generated by the following
grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|ε

(a){ambn | m >= n, n > 0}
(b){ambn | m >= n, n > =0}
(c){ ambn | m > n, n > =0 }
(d){ ambn | m > n, n > 0 }

year not read yetQ25 · page 228 of the book

Language L1 is defined by the grammar:
S1 → aS1b|ε
Language L2 is defined by the grammar:
S2 → abS2|ε
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?

(a)Both P and Q are true
(b)P is true and Q is false
(c)P is false and Q is true
(d)Both P and Q are false

GATE 2016 · Set 1 · MCQ · 2 marksQ28 · page 229 of the book

Consider the following context-free grammars:
G1:
S → aS|B,
B → b|bB
G2:
S → aA|bB,
A → aA|B|ε,
B → bB|ε.
Which one of the following pairs of languages is
generated by G1 and G2, respectively?

(a){ambn | m > 0 or n > 0} and {ambn | m > 0 and n > 0}
(b){ambn | m > 0 and n > 0} and {ambn | m > 0 or n >= 0}
(c){ambn | m >= 0 or n > 0} and {ambn| m > 0 and n > 0}
(d){ambn | m >= 0 and n > 0} and {ambn | m > 0 or n > 0}

GATE 2009 · MCQQ33 · page 229 of the book

S → aSa | bSb | a | b
The language generated by the above grammar over the
alphabet is the set of:

(a)all palindromes
(b)all odd length palindromes
(c)strings that begin and end with the same symbol
(d)all even length palindromes

GATE 2008 · MCQ · 1 markQ34 · page 229 of the book

A CFG G is given with the following productions where
S is the start symbol,A is a non-terminal and a and b are
terminals.
S → aS | A
A →aAb | bAa | ∈
Which of the following strings is generated by the
grammar above?

(a)aabbaba
(b)aabaaba
(c)abababb
(d)aabbaab THEORY OF COMPUTATION

GATE 2008 · MCQ · 2 marksQ35 · page 230 of the book

Consider a CFG with the following productions
S → AA | B
A →0A | A0 | 1
B → 0B00 | 1
S is the start symbol, A and B are non-terminals and 0
and 1 are the terminals. The language generated by this
grammar is :

(a){ 0n102n|n≥1}
(b){0i10j10k |i,j,k≥0}∪{ 0n102n|n≥0}
(c){0i10j |i,j≥0}∪{ 0n102n|n≥0}
(d)The set of all strings over {0,1} containing at least two 0's

year not read yetQ36 · page 230 of the book

Match the following:

E. Checking that
identifiers are
declared before
their use
P. L={ anbmcndm |n≥1,m≥1}
F. Number of formal
parameters in the
declaration of a
function agrees with
the number of actual
parameters in a use of
that function
Q. X→XbX | XcX | dXf | g
G. Arithmetic
expressions with
matched pairs of
parentheses
R. L={wcw|w∈ (a+b)* }
H. Palindromes
S. X→bXb | cXc | ε

(a)E-P, F-R, G-Q, H-S.
(b)E-R, F-P, G-S, H-Q
(c)E-R, F-P, G-Q, H-S
(d)E-P, F-R, G-S, H-Q

year not read yetQ38 · page 230 of the book

Consider the grammar given below:
S → x B | yA
A → x | xS | y A A
B → y | yS | x B B
Consider the following strings.
i. xxyyx
ii. xxyyxy
iii. xyxy
iv. yxxy
v. yxx
vi. xyx
Which of the above strings are generated by the
grammar?

(a)i, ii and iii
(b)ii, v and vi
(c)ii, iii and iv
(d)i, iii and iv

GATE 2007 · MCQ · 2 marksQ39 · page 230 of the book

The two grammars given below generate a language over
the alphabet {x,y,z}
G1: S → x | z | xS | zS | yB
B → y | z | yB |zB
G2: S →y | z | yS | zS | xB
B →y | yS
Which one of the following choices describes the
properties satisfied by the strings in these languages?

(a)G1 : No y appears before any x G2 : Every x is followed by at least one y.
(b)G1 : No y appears before any x G2 : No x appears before any y
(c)G1 : No y appears after any x G2 : Every x is followed by at least one y
(d)G1 : No y appears after any x G2 : Every y is followed by atleast one x

GATE 2006 · MCQ · 1 markQ42 · page 231 of the book

In the context-free grammar below, is the start symbol,
and are terminals, and denotes the empty string.
S →aSAb | ∈
A → bA | ∈
The grammar generates the language

(a)((a+b)*b)
(b)(ambn | m≤n )
(c)(ambn | m=n )
(d)a*b*

GATE 2006 · MCQ · 1 markQ43 · page 231 of the book

In the context-free grammar below,S is the start
symbol,a and b are terminals, and ∈ denotes the empty
string
S →aSa | bSb | a | b | ∈
Which of the following strings is NOT generated by
the grammar?

(a)aaaa
(b)baba
(c)abba
(d)babaaabab

Self-check

Question 1

Give a grammar for $\{a^n b^{2n} : n \ge 0\}$ and the number of derivation steps for $a^3 b^6$ .

Show answer

$S \to a S b b \mid \varepsilon$ ; $4$ steps ( $3$ uses of the first production and $1$ of the second).

Question 2

Why is $S \to aSa \mid bSb \mid \varepsilon$ not a grammar for all palindromes?

Show answer

It generates only even-length palindromes: odd ones such as $a$ and $aba$ need a single middle symbol ( $S \to a \mid b$ ).

Question 3

A parse tree has how many leftmost derivations? How many derivations in all, for the tree of $aabbb$ above?

Show answer

Exactly one leftmost derivation; $10$ derivations in all (the interleavings of the two chains).

Question 4

Is every regular language context-free? Show how for "ends with $01$ ".

Show answer

Yes: one variable per DFA state, $A_q \to a A_{\delta(q, a)}$ and $A_q \to \varepsilon$ for accepting $q$ .

Revision card

One-screen revision

$G = (V, \Sigma, R, S)$ ; derivations $\Rightarrow$ , $\Rightarrow^*$ ; $L(G)$ ; parse tree, yield.
One parse tree: one leftmost and one rightmost derivation, many others.
Standard grammars: $a^nb^n$ , palindromes, balanced, equal counts, union for $i = j$ or $j = k$ .
Regular $\subset$ CFL. Beware $S \to aSb \mid SS \mid \varepsilon$ (balanced, not equal counts).

References

·Sipser, Introduction to the Theory of Computation (3rd edition), Section 2.1 (context-free grammars)
·Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition), Chapter 5 (context-free grammars and languages)
·Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (2nd edition), Section 4.2 (context-free grammars)

Verification

scripts/enum-checks/toc_cfg.py: every grammar in the design table generates exactly the language of an independent predicate on all strings up to length 10 (over the alphabet of the language); the string counts per length were compared with the closed forms (1, 2^(n/2), 2^ceil(n/2), Catalan numbers, central binomial coefficients); the leftmost and rightmost derivation traces were replayed step by step and their trees read the string; the number of derivations of aabbb in all orders of expansion (10 = C(5, 2)) was found by exhaustive search; the right-linear grammar built from the DFA for 'ends with 01' generates that language on all strings up to length 10 and gives every string exactly one parse tree; the wrong grammar S -> aSb | SS | epsilon was shown to generate the balanced strings (with a as the opening symbol), not the strings with equal counts. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (state counts, derivations, parse-tree and move counts, decomposition counts); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Myhill-Nerode theorem

Ambiguity in grammars