Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

The product of mental labor — science — always stands far below its value, because thelabor-time necessary to reproduce it has no relation at all to the labor-time required for its
original production. For example, a schoolboy can learn the binomial theorem in an hour.
— Karl Marx, Theories of Surplus Value (1863)
Imagine a piano keyboard, eh, 88 keys, only 88 and yet, and yet, hundreds of new melodies,
new tunes, new harmonies are being composed upon hundreds of different keyboards every
day in Dorset alone. Our language, tiger, our language: Hundreds of thousands of available
words, frillions of legitimate new ideas, so that I can say the following sentence and beutterly sure that nobody has ever said it before in the history of human communication:“Hold the newsreader’s nose squarely, waiter, or friendly milk will countermand
my trousers.” Perfectly ordinary words, but never before put in that precise order. A uniquechild delivered of a unique mother.
— Stephen Fry, A Bit of Fry and Laurie, Series 1, Episode 3 (1989)

5

Context-Free Languages and Grammars

5.1

Definitions

Intuitively, a language is regular if it can be built from individual strings by concatenation, union,
and repetition. In this note, we consider a wider class of context-free languages, which arelanguages that can be built from individual strings by concatenation, union, and recursion.
Formally, a language is context-free if and only if it has a certain type of recursive description
known as a context-free grammar, which is a structure with the following components:• A finite set Σ, whose elements are called symbols or terminals.
• A finite set Γ disjoint from Σ, whose elements are called non-terminals.
• A finite set R of production rules of the form A → w, where A ∈ Γ is a non-terminal andw ∈ (Σ ∪ Γ )∗ is a string of symbols and variables.
• A starting non-terminal, typically denoted S.
For example, the following eight production rules describe a context free grammar with terminals
Σ = {0, 1} and non-terminals Γ = {S, A, B, C}:
S→A

A → 0AB → B1

C →"S→B

A → 0C

B → C1

C → 0C 1

Normally we write grammars more compactly by combining the right sides of all rules foreach non-terminal into one list, with alternatives separated by vertical bars.1 For example, theprevious grammar can be written more compactly as follows:
S →A| BA → 0A | 0C
B → B1 | C 1
C → " | 0C 1
1Yes, this means we now have three symbols ∪, +, and | with exactly the same meaning. Sigh.
© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

For the rest of this lecture, I will almost always use the following notational conventions.
• Monospaced digits (0, 1, 2, . . . ), and symbols (, $, #, •, . . . ) are explicit terminals.
• Early lower-case Latin letters (a, b, c, . . . ) represent unknown or arbitrary terminals in Σ.
• Upper-case Latin letters (A, B, C, . . . ) and the letter S represent non-terminals in Γ .
• Late lower-case Latin letters (. . . , w, x, y, z) represent strings in (Σ ∪ Γ )∗ , whose characters
could be either terminals or non-terminals.
We can apply a production rule to a string in (Σ ∪ Γ )∗ by replacing any instance of the
non-terminal on the left of the rule with the string on the right. More formally, for any strings
x, y, z ∈ (Σ ∪ Γ )∗ and any non-terminal A ∈ Γ , applying the production rule A → y to the stringxAz yields the string x yz. We use the notation x Az
x y z to describe this application. For
example, we can apply the rule C → 0C 1 to the string 00C 1BAC 0 in two different ways:

00 C 1BAC 0

00 0C 1 1BAC 0

00C 1BA C 0

00C 1BA 0C 1 0

More generally, for any strings x, z ∈ (Σ ∪ Γ )∗ , we say that z derives from x , written x ∗ z,
if we can transform x into z by applying a finite sequence of production rules, or more formally,
if either• x = z, or• xy and y∗z for some string y ∈ (Σ ∪ Γ )∗ .

Straightforward definition-chasing implies that, for any strings w, x, y, z ∈ (Σ ∪ Γ )∗ , if x ∗ y,then wxz ∗ w yz.
The language L(w ) of any string w ∈ (Σ ∪ Γ )∗ is the set of all strings in Σ∗ that derive from w:
L(w) := {x ∈ Σ∗ | w

∗

x} .

The language generated by a context-free grammar G, denoted L(G), is the language of its
starting non-terminal. Finally, a language is context-free if it is generated by some context-freegrammar.
Context-free grammars are sometimes used to model natural languages. In this context, thesymbols are words, and the strings in the languages are sentences. For example, the following
grammar describes a simple subset of English sentences. (Here I diverge from the usual notation
conventions. Strings in 〈angle brackets〉 are non-terminals, and regular strings are terminals.)〈sentence〉 → 〈noun phrase〉〈verb phrase〉〈noun phrase〉〈noun phrase〉 → 〈adjective phrase〉〈noun〉〈adj. phrase〉 → 〈article〉 | 〈possessive〉 | 〈adjective phrase〉〈adjective〉〈verb phrase〉 → 〈verb〉 | 〈adverb〉〈verb phrase〉〈noun〉 → dog | trousers | daughter | nose | homework | time lord | pony | · · ·〈article〉 → the | a | some | every | that | · · ·〈possessive〉 → 〈noun phrase〉’s | my | your | his | her | · · ·〈adjective〉 → friendly | furious | moist | green | severed | timey-wimey | little | · · ·〈verb〉 → ate | found | wrote | killed | mangled | saved | invented | broke | · · ·〈adverb〉 → squarely | incompetently | barely | sort of | awkwardly | totally | · · ·2Models of Computation

5.2

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Parse Trees

It is often useful to visualize derivations of strings in L(G) using a parse tree. The parse tree fora string w ∈ L(G) is a rooted ordered tree where• Each leaf is labeled with a terminal or the empty string ". Concatenating these in orderfrom left to right yields the string w.
• Each internal node is labeled with a non-terminal. In particular, the root is labeled withthe start non-terminal S.
• For each internal node v, there is a production rule A → ω where A is the label of v andthe symbols in ω are the labels of the children of v in order from left to right.
In other words, the production rules of the grammar describe template trees that can beassembled into larger parse trees. For example, the simple grammar on the previous page has
the following templates, one for each production rule:
S

S

A

A

B

A

B

0 A

0 C

B 1

B
C

1

C

C

"

0 C

1

The same grammar gives us the following parse tree for the string 000011:
S
A

0

A

0

C

0

1

C

0 C 1
"

Our more complicated “English” grammar gives us parse trees like the following:〈sentence〉〈noun phrase〉〈adj. phrase〉〈adj. phrase〉〈adj. phrase〉 〈adjective〉〈posessive〉〈noun phrase〉〈verb phrase〉〈noun〉 〈adverb〉 〈verb phrase〉〈adjective〉 time lord barely
green〈adj. phrase〉 〈noun〉〈posessive〉 trousers〈verb〉
mangled〈noun phrase〉 ’s〈adj. phrase〉 〈noun〉

furious〈possessive〉

your

dog

my

Any parse tree that contains at least one node with more than one non-terminal child corresponds
to several different derivations. For example, when deriving an “English” sentence, we have a
choice of whether to expand the first 〈noun phrase〉 (“your furious green time lord”) before orafter the second (“my dog’s trousers”).

3Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

A string w is ambiguous with respect to a grammar if there is more than one parse tree for w,
and a grammar G is ambiguous is some string is ambiguous with respect to G. Neither of theprevious example grammars is ambiguous. However, the grammar S → 1 | S +S is ambiguous,
because the string 1+1+1+1 has five different parse trees:
S
S

+ S

S

1

S +

S

1

S + S

+ S

S
S + S

1

S

1

1

+ S

1

S

S

1
1

+

S

S +

S

S + S

S + S

1

1

1

S

S

+ S

S + S

1

1

1

S +

S

1

1

1

S
S +

S

1

S + S

1

1

A context-free language L is inherently ambiguous if every context-free grammar thatgenerates L is ambiguous. The language generated by the previous grammar (the regular
language (1+)∗ 1) is not inherently ambiguous, because the unambiguous grammar S → 1 | 1+S
generates the same language.

5.3

From Grammar to Language

Let’s figure out the language generated by our first example grammar
S →A| BA → 0A | 0C

B → B1 | C 1

C → " | 0 C 1.

Since the production rules for non-terminal C do not refer to any other non-terminal, let’s begin
by figuring out L(C). After playing around with the smaller grammar C → " | 0C 1 for a few
seconds, you can probably guess that its language is {", 01, 0011, 000111, . . .}, that is, theset all of strings of the form 0n 1n for some integer n. For example, we can derive the string
00001111 from the start non-terminal S using the following derivation:
C

0C 1

00C 11000C 111

0000C 1111

0000" 1111 = 00001111

The same derivation can be viewed as the following parse tree:
C

0

1

C

0

1

C

0

1

C

0

C

1

"

In fact, it is not hard to prove by induction that L(C) = {0n 1n | n ≥ 0} as follows. As usual when
we prove that two sets X and Y are equal, the proof has two stages: one stage to prove X ⊆ Y ,the other to prove Y ⊆ X .
Lemma 5.1. C∗

0n 1n for every non-negative integer n.

Proof: Fix an arbitrary non-negative integer n. Assume that C
integer k < n. There are two cases to consider.
4∗0k 1k for every non-negativeModels of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]• If n = 0, then 0n 1n = ". The rule C → " implies that C" and therefore C• Suppose n > 0. The inductive hypothesis implies that C
C → 0C 1 implies that C
0C 1 ∗ 0(0n−1 1n−1 )1 = 0n 1n .
In both cases, we conclude that that C

∗

∗

∗

".

0n−1 1n−1 . Thus, the rule0n 1n , as claimed.

Lemma 5.2. For every string w ∈ L(C), we have w = 0n 1n for some non-negative integer n.
Proof: Fix an arbitrary string w ∈ L(C). Assume that for any string x ∈ L(C) such that |x| < |w|,
we have x = 0k 1k for some non-negative integer k. There are two cases to consider, one for eachproduction rule.
• If w = ", then w = 00 10 .
• Otherwise, w = 0 x 1 for some string x ∈ L(C). Because |x| = |w| − 2 < |w|, the inductive
hypothesis implies that x = 0k 1k for some integer k. Then we have w = 0k+1 1k+1 .
In both cases, we conclude that w = 0n 1n for some non-negative integer n, as claimed.

The first proof uses induction on strings, following the boilerplate proposed in the very firstlecture; in particular, the case analysis mirrors the recursive definition of “string”. The second
proof uses structural induction on the parse tree of the string 0n 1n ; the case analysis mirrors
the recursive definition of the language of S, as described by the production rules. In bothproofs, as in every proof by induction, the inductive hypothesis is “Assume there is no smaller
counterexample.”
Similar analysis implies that L(A) = {0m 1n | m > n} and L(B) = {0m 1n | m < n}, andtherefore L(S) = {0m 1n | m 6= n}.
5.3.1

Careful With Those Epsilons

There is an important subtlety in the proof of Lemma 5.2. The proof is written as induction on
the length of the string w; unfortunately, this induction pattern does not work for all context-freegrammars. Consider the following ambiguous grammar
S → " | SS | 0S 1 | 1S 0.
A bit of experimentation should convince you that L(S) is the language of all binary strings withthe same number of 0s and 1s. We cannot use the string-induction boilerplate for this grammar,
because there are arbitrarily long2 derivations of the form
S

SS

S

SS

S

SS

SS

···

w,

which alternately apply the productions S → SS and S → ". Specifically, even if we knew that
our arbitrary string w can be written as x y for some strings x, y ∈ L(S), we cannot guaranteethat |x| < |w| and | y| < |w|, to we cannot apply the standard string-induction hypothesis.
However, we can still argue inductively about this grammar, by considering a minimum-length
derivation of w, and basing the case analysis on the first production in this derivation. Here’s
an example of this induction boilerplate in action, with the modified boilerplate language
highlighted.
2but not infinite; derivations are finite by definition!

5Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Lemma 5.3. For every string w ∈ L(S), we have #(0, w) = #(1, w).
Proof: Let w be an arbitrary string in L(S). Fix an minimum-length derivation of w.
Assume that for any string x ∈ L(S) that is shorter than w, we have x = 0k 1k for some
non-negative integer k. There are four cases to consider, depending on the first production in our
fixed derivation.
• Suppose the first production is S → ". Then w = " and therefore #(0, w) = #(1, w) = 0 by
definition.
• Suppose the first production is S → SS. Then w = x y for some strings x, y ∈ L(S). Bothx and y must be non-empty; otherwise, we could shorten our derivation of w. Thus,
both x and y are shorter than w. The inductive hypothesis implies #(0, x) = #(1, x) and#(0, y) = #(1, y), so #(0, w) = #(0, x) + #(0, y) = #(1, x) + #(1, y) = #(1, w).
• Suppose the first production is S → 0S 1. Then w = 0 x 1 for some string x ∈ L(S). The
inductive hypothesis implies #(0, x) = #(1, x) so #(0, w) = #(0, x) + 1 = #(1, x) + 1 =#(1, w).
• Finally, suppose the first production is S → 1S 0. Then w = 1 x 0 for some string x ∈ L(S).
The inductive hypothesis implies #(0, x) = #(1, x) so #(0, w) = #(0, x) + 1 = #(1, w) +1 = #(1, w).
In all cases, we conclude that #(0, w) = #(1, w), as claimed.



Another (more traditional) way to handle this issue is to fix an arbitrary derivation, and theninduct on the length of the derivation, rather than the length of the string itself. The case analysis
is still based on the first production in the chosen derivation.
In fact, this subtlety only matters for grammars that either contain a nullable non-terminal A
such that A ∗ " or equivalent nonterminals A and B such that A ∗ B and B ∗ A. We describe
algorithms to identify these pathologies and remove them from the grammar (without changing
its language) in Section 5.9 below.
5.3.2

Mutual Induction

Another pitfall in induction proofs for context-free languages is that non-terminals may invoke
each other. Consider, for example, the grammar
S → 0A1 | "A → 1S 0 | "Because each non-terminal appears on the right side of a production rule for the other, we mustargue about L(S) and L(A) simultaneously.
Lemma 5.4. L(S) = (01)∗ .
Proof: We actually prove simultaneously that L(S) = (01)∗ and L(A) = (10)∗ .
First, we claim that for any non-negative integer n, we have (01)n ∈ L(S) and (10)n ∈ L(A).
Let n be an arbitrary non-negative integer, and assume, for all non-negative integers m < n, that(01)m ∈ L(S) and (10)m ∈ L(A). There are two cases to consider.
• If n = 0, the production rules S → " and A → " immediately imply S
A " = (10)n .
6" = (01)n andModels of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]• Suppose n > 0. We easily observe that (01)n = 0(10)n−1 1, so the production rule S → 0A1
and inductive hypothesis imply S
0A1 ∗ (01)n . Symmetrically, (10)n = 1(01)n−1 0, so
the production rule A → 1S 0 and the inductive hypothesis implies A 1S 0 ∗ (10)n .
Next we claim that for every string w ∈ L(S), we have w = (01)n for some non-negative
integer n, and for every string w ∈ L(A), we have w = (10)n for some non-negative integer n.
The proof requires two stages.
• Let w be an arbitrary string in L(S), and assume for all x ∈ L(A) such that |x| < |w| thatx = (10)n for some non-negative integer n. There are two cases to consider.
– If w = ", then w = (01)0 .
– Suppose w = 0 x 1 for some string x ∈ L(A). The inductive hypothesis implies
x = (10)n for some non-negative integer n. It follows that w = 0(10)n 1 = (01)n+1 .
• Let w be an arbitrary string in L(A), and assume for all x ∈ L(S) such that |x| < |w| thatx = (01)n for some non-negative integer n. There are two cases to consider.
– If w = ", then w = (10)0 .
– Suppose w = 1 x 0 for some string x ∈ L(S). The inductive hypothesis implies
x = (01)n for some non-negative integer n. It follows that w = 1(01)n 0 = (10)n+1 .
Together these two claims imply L(S) = (01)∗ and L(A) = (10)∗ , as required.

5.4

More Examples

Here are some more examples of context-free languages and grammars that generate them,along with brief sketches of correctness proofs.
• Palindromes in {0, 1}∗ :S → 0S 0 | 1S 1 | 0 | 1 | "This grammar is a straightforward translation of the recursive definition of palindrome.
• Strings in (0 + 1)∗ that are not palindromes.
S → 0S 0 | 1S 1 | 0 Z 1 | 1 Z 0
Z → " | 0Z | 1Z
A string w is a non-palindrome if and only if w = x 0z 1 x R or w = x 1z 0 x R for some(possibly empty) strings x and y.
• Strings in {0, 1}∗ with the same number of 0s and 1s:
S → 0S 1 | 1S 0 | SS | "A non-empty string w has the same number of 0s and 1s if and only one of the following
conditions holds:– We can write w = x y for some non-empty strings x and y such that #(0, x) = #(1, x)
and #(0, y) = #(1, y).
7Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]– #(0, x) > #(1, x) for every non-empty proper prefix x of w. In this case, w = 0z 1
for some string z with #(0, z) = #(1, z).
– #(0, x) < #(1, x) for every non-empty proper prefix x of w. In this case, w = 1z 0
for some string z with #(0, z) = #(1, z).
• Strings in {0, 1}∗ with the same number of 0s and 1s, again:
S → 0S 1S | 1S 0S | "Let w be any non-empty string such that #(0, w) = #(1, w), let x be the shortest non-empty
prefix of w such that #(0, x) = #(1, x), and let y be the complementary suffix of w, so
w = x y. It is not hard to prove that x begins and ends with different symbols, so either
w = 0z 1 y or w = 1z 0 y, where #(0, y) = #(1, y) and #(0, z) = #(1, z).
• Strings in {0, 1}∗ in which the number of 0s is greater than or equal to the number of 1s:
S → 0S 1 | 0S | 1S 0 | S 0 | SS | "S → 0S 1S | 0SS | 1S 0S | S 0S | "We have to different grammars, each constructed from a grammar for strings with equal 0s
and 1s by either dropping the 1 or keeping the 1 from the right side of each production rule
containing a 1. For example, we split the production rule S → 0S 1 in the first grammar
into two production rules S → 0S 1 and S → 0S.
If we add the trivial production S → 0 to the first grammar, we can remove two
redundant productions to get the simpler grammar
S → 0S 1 | 1S 0 | SS | 0 | "• Strings in {0, 1}∗ with different numbers of 0s and 1s:
S→O|I(different)

O → E 0O | E 0 E(more 0s)

I → E1I | E1E(more 1s)

E → 0E1E | 1E0E | "(equal)We can argue correctness by considering each non-terminal in turn, in reverse order.
– E generates all strings with the same number of 0s and 1s, as in the previous example.
– I generates all strings with more 1s than 0s. Any such string can be decomposed into
its longest prefix with the same number of 0s and 1s (E), followed by a 0, followed
by a suffix with at least as many 0s as 1s (I or E).
– Symmetrically, O generates all strings with more 0s than 1s.
– Finally, S generates all strings with different numbers of 0s and 1s. Any such string
either has more 0s (O) or more 1s (I)• Balanced strings of parentheses:
S → (S ) | SS | "orS → (S )S | "Here we have two grammars for the same language. The first one uses simpler productions,and is a bit closer to the natural recursive definition. However, the first grammar is8Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

ambiguous — consider the string ()()() — while the second grammar is not. The second
grammar decomposes any balanced string of parentheses into its shortest non-empty
balanced prefix, which must start with ( and end with ), and the remaining suffix, whichmust be balanced.
• Unbalanced strings of parentheses—the complement of the previous language:
S → L | RX(unbalanced)

L → E( L | E(E(more left parens)

R → E )R | E ) E(more right parens)

E → " | (E)E | )E(E(equal left and right)

X → " | (X | )X

(anything)A string w of parens is balanced if and only if both (a) w has the same number of left andright parens and (b) no prefix of w has more right parens than left parens. (Proving thisfact is a good homework exercise.) Thus, a string w of parens is unbalanced if and only ifeither w has more left parens than right parens or some prefix of w has more right parens
than left parens.
• Arithmetic expressions, possibly with redundant parentheses, over the variables X and Y:
E → E+T | T(expressions)

T → T×F | F(terms)F → (E) | X | Y(factors)

Every Eexpression is a sum of T erms, every T erm is a product of F actors, and every F actor
is either a variable or a parenthesized Eexpression.
• Regular expressions over the alphabet {0, 1} without redundant parentheses
S → T | T +S

(Regular expressions)

T → F | FT

(Terms = summable expressions)

F → Ø | W | ( T +S ) | X * | (Y )*(Factors = concatenable expressions)

X →Ø|3|0|1(Directly starrable expressions)

Y → T +S | F • T | X * | (Y )* | Z Z(Starrable expressions needing parens)

W →3|Z(Words = strings)

Z → 0 | 1 | ZZ

(Non-empty strings)

Every regular expression is a sum of terms; every term is a concatenation of factors. Everyfactor is either the empty-set symbol, a string, a nontrivial sum of terms in parens, or astarred expression. The expressions Ø*, 3*, 0*, and 1* require no parentheses; otherwise,
the starred subexpression is either a nontrivial sum of terms, a nontrivial concatenation offactors, a starred expression, or a string of length 2 or more.
The “epsilon” symbol 3 in the production rules for W and Z does not represent theempty string per se, but rather an actual symbol that might appear in a regular expression.
The empty string is not a regular expression, but the one-symbol string 3 is a regularexpression that represents the set containing only the empty string!
9Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

The final grammar illustrates an important subtlety for certain applications of context-freegrammars. This grammar is considerably more complicated than one might initially expect fromthe definition of regular languages. It’s tempting to suggest a much simpler grammar likeS → Ø | 3 | 0 | 1 | S +S | SS | S * | (S )but this is incorrect! This grammar does correctly generate all regular expressions as raw strings,
but it allows parse trees that do not respect the meaning of the regular expression. For example,
this “simpler” grammar can parse the regular expression string 0*+1* in two different ways:
S
S

S*

S +S
S*

0 *

+

S +S

S*

S*

1 *

*

+ 1

0 *
The first tree correctly parses the regular expression string 1*+0* as the expression (1∗ ) + (0∗ )but without the redundant parentheses. The second tree incorrectly parses the same string as(1∗ + 0)∗ , which describes a very different regular language!

5.5

Regular Languages are Context-FreeThe following inductive argument proves that every regular language is also a context-freelanguage. Let L be an arbitrary regular language, encoded by some regular expression R. Assume
that any regular expression simpler than R represents a context-free language. (“Assume nosmaller counterexample.”) We construct a context-free grammar for L as follows. There areseveral cases to consider.
• Suppose L is empty. Then L is generated by the trivial grammar S → S.
• Suppose L = {w} for some string w ∈ Σ∗ . Then L is generated by the grammar S → w.
• Suppose L is the union of some regular languages L1 and L2 . The inductive hypothesis
implies that L1 and L2 are context-free. Let G1 be a context-free language for L1 withstarting non-terminal S1 , and let G2 be a context-free language for L2 with starting nonterminal S2 , where the non-terminal sets in G1 and G2 are disjoint. Then L = L1 ∪ L2 isgenerated by the production rule S → S1 | S2 .
• Suppose L is the concatenation of some regular languages L1 and L2 . The inductive
hypothesis implies that L1 and L2 are context-free. Let G1 be a context-free language forL1 with starting non-terminal S1 , and let G2 be a context-free language for L2 with starting
non-terminal S2 , where the non-terminal sets in G1 and G2 are disjoint. Then L = L1 L2 isgenerated by the production rule S → S1 S2 .
• Suppose L is the Kleene closure of some regular language L1 . The inductive hypothesis
implies that L1 is context-free. Let G1 be a context-free language for L1 with starting
non-terminal S1 . Then L = L1∗ is generated by the production rule S → " | S1 S.
In every case, we have found a context-free grammar that generates L, which means L iscontext-free.
In the previous lecture note, we proved that the context-free language {0n 1n | n ≥ 0} is not
regular. (In fact, this is the canonical example of a non-regular language.) Thus, context-freegrammars are strictly more expressive than regular expressions.
10Models of Computation

5.6

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Not Every Language is Context-Free

Again, you may be tempted to conjecture that every language is context-free, but a variant of ourearlier cardinality argument implies that this is not the case.
Any context-free grammar over the alphabet Σ can be encoded as a string over the alphabetΣ ∪ Γ ∪ {3, K, |, $}, where $ indicates the end of the production rules for each non-terminal. For
example, our example grammar
A → 0A | 0 C

S →A| BB → B1 | C 1

C → " | 0C 1

can be encoded as the string

SKA|B$AK0A|0C$BKB1|C1$CK3|0C1$
We can further encode any such string as a binary string by associating each symbol in theset Σ ∪ Γ ∪ {3, K, |, $} with a different binary substring. Specifically, if we encode each of thegrammar symbols 3, K, |, $ as a string of the form 11∗ 0, each terminal in Σ as a string of theform 011∗ 0, and each non-terminal as a string of the form 0011∗ 0, we can unambiguously
recover the grammar from the encoding. For example, applying the code

3 7→ 10

0 7→ 010

S 7→ 0010

K 7→ 110

1 7→ 0110

A 7→ 00110| 7→ 1110

B 7→ 001110$ 7→ 11110

C 7→ 0011110

transforms our example grammar into the 136-bit string

00101100011011100011101111000110
11001000110111001000111101111000
11101100011100110111000111100110
11110001111011010111001000111100
11011110.
Adding a 1 to the start of this bit string gives us the binary encoding of the integer
102 231 235 533 163 527 515 344 124 802 467 059 875 038.
Our construction guarantees that two different context-free grammars over the same alphabet(ignoring changing the names of the non-terminals) yield different positive integers. Thus, theset of context-free grammars over any alphabet is at most as large as the set of integers, and istherefore countably infinite. (Most integers are not encodings of context-free grammars, but that
only helps us.) It follows that the set of all context-free languages over any fixed alphabet isalso countably infinite. But we already showed that the set of all languages over any alphabet isuncountably infinite. So almost all languages are non-context-free!
There are techniques for proving that specific languages are not context-free, just as there
are for proving certain languages are not regular; unfortunately, they are beyond the scope of
this course. In particular, the {0n 1n 0n | n ≥ 0} is not context-free. (In fact, this is the canonicalexample of a non-context-free language.)11Models of Computation?

5.7

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Recursive Automata

All the flavors of finite-state automata we have seen so far describe/encode/accept/compute
regular languages; these are precisely the languages that can be constructed from individual
strings by union, concatenation, and unbounded repetition. Just as context-free grammars arerecursive generalizations of regular expressions, we can define a class of machines called recursive
automata, which generalize (nondeterministic) finite-state automata. Recursive automata wereintroduced by Walter Woods in 1970 for natural language parsing; Wodds’ terminology recursive
transition networks is more common among computational linguists.
Formally, a recursive automaton consists of the following components:• A non-empty finite set Σ, called the input alphabet• Another non-empty finite set N , disjoint from Σ, whose elements are called module names• A start name S ∈ N• A set M = {MA | A ∈ N } of NFAs, called modules, over the alphabet Σ ∪ N . Each module
MA has the following components:– A finite set Q A of states, such that Q A ∩ Q B = ∅ for all A 6= B
– A start state sA ∈ Q A– A unique terminal or accepting state t A ∈ Q A– A nondeterministic transition function δA : Q A × (Σ ∪ {"} ∪ N ) → 2Q A .
Equivalently,
we have a single global transition function δ : Q × (Σ ∪ {"} ∪ N ) → 2Q , whereS
Q = A∈N Q A, such that for any name A and any state q ∈ Q A we have δ(q) ⊆ Q A. Machine MS iscalled the main module.
A configuration of a recursive automaton is a triple (w, q, s), where w is a string in Σ∗ called
the input, q is a state in Q called the local state, and σ is a string in Q∗ called the stack. The
module containing the local state q is called the active module. A configuration can be changedby three types of transitions.
• A read transition consumes the first symbol in the input and changes the local state within
the active module, just like a standard NFA.
• An epsilon transition changes the local state within the active module, without consuming
any input characters, just like a standard NFA.
• A call transition chooses a module name A, pushes some state in δ(q, A) onto the stack,and then changes the local state to sA (thereby changing the active module to MA), without
consuming any input characters.
• Finally, if the current state is the terminal state of the active module and the stack is
non-empty, a return transition pops the top state off the stack and makes it the new
local state (thereby possibly changing the active module), without consuming any input
characters.
Symbolically, we can describe these transitions as follows:


read:
a x, q, σ 7−→ x, q0 , σ
for some q0 ∈ δ(q, a)epsilon:w, q, σ 7−→ w, q0 , σ
for some q0 ∈ δ(q, ")


call:
w, q, σ 7−→ w, sA, q0 · σ
for some A ∈ N and some q0 ∈ δ(q, A)
return:w, t A, q · σ 7−→ w, q, σ
12Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

A recursive automaton accepts a string w if there is a finite sequence of transitions starting at thestart configuration (w, sS , ") and ending at the terminal configuration (", t S , ").

ÆÆÆ

Reformulate recursive automata using recursion-as-magic, analogously to the nondeterminism-as-magic in string NFAs or Han and Wood’s expression automata. A recursive
automaton module MA accepts a string w if any only if there is a finite sequence of transitions
α1

α3

α2

α`

sA = q0 −→ q1 −→ q2 −→ · · · −→ q` = t Aamong states in Q A, and a decomposition of w into substrings x 1 • x 2 • · · · • x ` , where one of
the following conditions holds for each index i :• αi = " and x i = "• αi ∈ Σ and x i = αi
• αi ∈ N and module Mαi accepts x i .
This model is then easily extended to more general transition labels:• Recursive string-automata allow transitions to be labeled by either strings in Σ∗ ormodule names, and the first two bullets in the previous list become “αi = x i ”.
• Recursive expression-automata allow transitions to be labeled by either regular expressions over Σ or module names, and the first two bullets in the previous list become “αiis a regular expression and x i matches αi ”.
• We could even consider recursive-expression automata, which allow transitions to belabeled by arbitrary regular expressions over Σ ∪ N .
• We could even even consider recursive-grammar automata, which allow transitions to
be labeled by arbitrary context-free grammars over Σ ∪ N . WEEEE/EEEEW!

For example, the following recursive automaton accepts the language {0m 1n | m 6= n}. The
recursive automaton has two component modules; the start machine named S and a “subroutine”
named E (for “equal”) that accepts the language {0n 1n | n ≥ 0}. White arrows indicate recursive
transitions. The large arrow into each module indicates that module’s start state; the large arrowleading out of each module indicates that modules terminal state.

S

E
E

0

ε
1

0

1

0

E

1
E

A recursive automaton for the language {0m 1n | m 6= n}

Lemma 5.5. Every context-free language is accepted by a recursive automaton.
Proof:

ÆÆÆDirect construction from the CFG, with one module per nonterminal.



13Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

For example, the context-free grammar
S → 0A | B1
A → 0A | E
B → B1 | E
E → " | 0E0
leads to the following recursive automaton with four modules:ÆÆÆ

Figure!

Lemma 5.6. Every recursive automaton accepts a context-free language.
Proof (sketch): Let R = (Σ, N , S, δ, M ) be an arbitrary recursive automaton. We define acontext-free grammar G that describes the language accepted by R as follows.
The set of nonterminals in G is isomorphic the state set Q; that is, for each state q ∈ Q, thegrammar contains a corresponding nonterminal [q]. The language of [q] will be the set of strings
w such that there is a finite sequence of transitions starting at the start configuration (w, q, ")and ending at the terminal configuration (", t, "), where t is the terminal state of the module
containing q.
The grammar has four types of production rules, corresponding to the four types of transitions:• read: For each symbol a and each pair of states p and q such that p ∈ δ(q, a), the grammar
contains the production rule [q] → a[p].
• epsilon: For any two states p and q such that p ∈ δ(q, "), the grammar contains the
production rule [q] → [p].
• call: Each name A and each pair of states states p and q such that p ∈ δ(q, A), the grammar
contains the production rule [q] → [sA][p].
• return: Each name A, the grammar contains the production rule [t A] → ".
Finally, the starting nonterminal of G is [sS ], which corresponds to the start state of the main
module.
We can now argue inductively that the grammar G and the recursive automaton R describe
the same language. Specifically, any sequence of transitions in R from (w, sS , ") to (", t S , ") can betransformed mechanically into a derivation of w from the nonterminal [sS ] in G. Symmetrically,
the leftmost derivation of any string w in G can be mechanically transformed into an accepting
sequence of transitions in R. We omit the straightforward but tedious details.
For example, the recursive automaton on the previous page gives us the following context-freegrammar. To make the grammar more readable, I’ve renamed the nonterminals corresponding tostart and terminal states: S = [sS ], T = [t S ], and E = [s E ] = [t E ]:S → EA | 0B

E → " | 0X

A → 1A | 1 T

X → EYB → 0B | E T

Y → 1ZT →"Z→E

Our earlier proofs imply that we can forbid "-transitions or even allow regular-expression
transitions in our recursive automata without changing the set of languages they accept.
14

Models of Computation

5.8

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Chomsky Normal Form

For many algorithmic problems involving context-free grammars, it is helpful to consider
grammars with a particular special structure called Chomsky normal form, abbreviated CNF:
• The starting non-terminal S does not appear on the right side of any production rule.
• The starting non-terminal S may have the production rule S → ".
• The right side of every other production rule is either a single terminal symbol or a stringof exactly two non-terminals—that is, every other production rule has the form A → BC or
A → a.
A particularly attractive feature of CNF grammars is that they yield full binary parse trees; inparticular, every parse tree for a string of length n > 0 has exactly 2n − 1 non-terminal nodes.
Consequently, any string of length n in the language of a CNF grammar can be derived in exactly
2n − 1 production steps. It follows that we can actually determine whether a string belongs to
the language of a CNF grammar by brute-force consideration of all possible derivations of theappropriate length.
For arbitrary context-free grammars, there is no similar upper bound on the length of a
derivation, and therefore no similar brute-force membership algorithm, because the grammar
may contain additional "-productions of the form A → " and/or unit productions of the form
A → B, where both A and B are non-terminals. Unit productions introduce nodes of degree 1
into any parse tree, and "-productions introduce leaves that do not contribute to the word beingparsed.
Fortunately, it is possible to determine membership in the language of an arbitrary context-freegrammar, thanks to the following theorem. Two context-free grammars are equivalent if they
define the same language.
Every context-free grammar is equivalent to a grammar in Chomsky normal form.
Moreover, there are algorithms to automatically convert any context-free grammar into Chomsky
normal form. Unfortunately, these conversion algorithms are quite complex, but for mostapplications of context-free grammars, the details of the conversion are unimportant—it’s enoughto know that the algorithms exist. For the sake of completeness, however, I will describe one
such conversion algorithm in the next section.
?

5.9

CNF Conversion Algorithm

I’ll actually prove a stronger statement: Not only can we convert any context-free grammar into
Chomsky normal form, but we can do so quickly. We analyze the running time of our conversion
algorithm in terms of the total length of the input grammar, which is just the number of symbols
needed to write down the grammar. Up to constant factors, the total length is the sum of thelengths of the production rules.
Theorem 5.7. Given an arbitrary context-free grammar with total length L, we can compute anequivalent grammar in Chomsky normal form with total length O(L 2 ) in O(L 2 ) time.
Our algorithm consists of several relatively straightforward stages. Efficient implementationof some of these stages requires standard graph-traversal algorithms, which are described in adifferent part of the course.
15Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

0. Add a new starting non-terminal. Add a new non-terminal S 0 and a production rule S 0 → S,
where S is the starting non-terminal for the given grammar. S 0 will be the starting non-terminal
for the resulting CNF grammar. (In fact, this step is necessary only when S ∗ ", but at this pointin the conversion process, we don’t yet know whether that’s true.)
1. Decompose long production rules. For each production rule A → ω whose right side w has
length greater than two, add new production rules of length two that still permit the derivationA ∗ ω. Specifically, suppose ω = αχ for some symbol α ∈ Σ ∪ Γ and string χ ∈ (Σ ∪ Γ )∗ . The
algorithm replaces A → ω with two new production rules A → αB and B → χ, where B is a new
non-terminal, and then (if necessary) recursively decomposes the production rule B → χ. For
example, we would replace the long production rule A → 0BC 1C B with the following sequenceof short production rules, where each Ai is a new non-terminal:
A → 0A1

A1 → BA2

A2 → CA3

A3 → 1A4

A4 → C B

This stage can significantly increase the number of non-terminals and production rules, but it
increases the total length of all production rules by at most a small constant factor.3 Moreover,for the remainder of the conversion algorithm, every production rule has length at most two. The
running time of this stage is O(L).
2. Identify nullable non-terminals. A non-terminal A is nullable if and only if A ∗ ". The
recursive definition of ∗ implies that A is nullable if and only if the grammar contains a
production rule A → ω where ω consists entirely of nullable non-terminals (in particular, if
ω = "). You may be tempted to transform this recursive characterization directly into a recursivealgorithm, but this is a bad idea; the resulting algorithm would fall into an infinite loop if (forexample) the same non-terminal appeared on both sides of the same production rule. Instead, weapply the following fixed-point algorithm, which repeatedly scans through the entire grammar
until a complete scan discovers no new nullable non-terminals.
Nullables(Σ, Γ , R, S):Γ" ← ∅〈〈known nullable non-terminals〉〉done ← False
while ¬done
done ← Truefor each non-terminal A ∈ Γ \ Γ"for each production rule A → ω
if ω ∈ Γ∗"
add A to Γ"
done ← False
return Γ"

At this point in the conversion algorithm, if S 0 is not identified as nullable, then we can safely
remove it from the grammar and use the original starting nonterminal S instead.
As written, Nullables runs in O(nL) = O(L 2 ) time, where n is the number of non-terminals
in Γ . Each iteration of the main loop except the last adds at least one non-terminal to Γ" , so the
3In most textbook descriptions of the CFG conversion algorithm, this stage is performed last, after removing"-productions and unit productions. But with the stages in that traditional order, removing "-productions could
exponentially increase the length of the grammar in the worst case! Consider the production rule A → (BC)k , where B
is nullable but C is not. Decomposing this rule first and then removing "-productions introduces about 3k new rules;
whereas, removing "-productions first introduces 2k new rules, most of which then must then be further decomposed!

16Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

algorithm halts after at most n + 1 ≤ L iterations, and in each iteration, we examine at most L
production rules. There is a faster implementation of Nullables that runs in O(n + L) = O(L)time,⁴ but since other parts of the conversion algorithm already require O(L 2 ) time, we needn’t
bother.
3. Eliminate "-productions. First, remove every production rule of the form A → ". Then foreach production rule A → w, add all possible new production rules of the form A → w0 , where w0
is a non-empty string obtained from w by removing one nullable non-terminal. For example, if if
the grammar contained the production rule A → BC, where B and C are both nullable, we would
add two new production rules A → B | C. Finally, if the starting nonterminal S 0 was identified as
nullable in the previous stage, add the production rule S 0 → "; this will be the only "-productionin the final grammar. This phase of the conversion runs in O(L) time and at most triples thenumber of production rules.
4. Merge equivalent non-terminals. We say that two non-terminals A and B are equivalent if
they can be derived from each other: A ∗ B and B ∗ A. Because we have already removed"-productions, any such derivation must consist entirely of unit productions. For example, in thegrammar
S → B | C,

A → B | D | C C | 0,

B → C | AD | 1,

C → A | DA,

D → BA | C S,

non-terminals A, B, C are all equivalent, but S is not in that equivalence class (because we cannot
derive S from A) and neither is D (because we cannot derive A from D).
Construct a directed graph G whose vertices are the non-terminals and whose edges correspondto unit productions, in O(L) time. Then two non-terminals are equivalent if and only if they arein the same strong component of G. Compute the strong components of G in O(L) time using,for example, the algorithm of Kosaraju and Sharir. Then merge all the non-terminals in each
equivalence class into a single non-terminal. Finally, remove any unit productions of the form
A → A. The total running time for this phase is O(L). Starting with our example grammar above,
merging B and C with A and removing the production A → A gives us the simpler grammar
S → A,A → AA | D | DA | 0 | 1,

D → AA | AS.

We could further simplify the grammar by merging all non-terminals reachable from S using only
unit productions (in this case, merging non-terminals S and S), but this further simplification is
unnecessary.
5. Remove unit productions. Once again, we construct a directed graph G whose vertices are
the non-terminals and whose edges correspond to unit productions, in O(L) time. Because no
two non-terminals are equivalent, G is acyclic. Thus, using topological sort, we can index thenon-terminals A1 , A2 , . . . , An such that for every unit production Ai → A j we have i < j, againin O(L) time; moreover, we can assume that the starting non-terminal is A1 . (In fact, both thedag G and the linear ordering of non-terminals was already computed in the previous phase!!)Then for each index j in decreasing order, for each unit production Ai → A j and eachproduction A j → ω, we add a new production rule Ai → ω. At this point, all unit productions are
⁴Consider the bipartite graph whose vertices correspond to non-terminals and the right sides of production rules,
with one edge per rule. The faster algorithm is a modified breadth-first search of this graph, starting at the vertex
representing ".

17Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

redundant and can be removed. Applying this algorithm to our example grammar above gives us
the grammar
S → AA | AS | DA | 0 | 1,

A → AA | AS | DA | 0 | 1,

D → AA | AS.

In the worst case, each production rule for An is copied to each of the other n − 1 nonterminals. Thus, this phase runs in Θ(nL) = O(L 2 ) time and increases the length of the grammarto Θ(nL) = O(L 2 ) in the worst case.
This phase dominates the running time of the CNF conversion algorithm. Unlike previous
phases, no faster algorithm for removing unit transformations is known! There are grammars oflength L with unit productions such that any equivalent grammar without unit productions haslength Ω(L 1.499999 ) (for any desired number of 9s), but this lower bound does not rule out thepossibility of an algorithm that runs in only O(L 3/2 ) time. Closing the gap between Ω(L 3/2−" )and O(L 2 ) has been an open problem since the early 1980s!
6. Protect terminals. Finally, for each terminal a ∈ Σ, we introduce a new non-terminal Aa
and a new production rule Aa → a, and then replace a with Aa in every production rule oflength two.
This completes the conversion to Chomsky normal form! As claimed, the total running timeof the algorithm is O(L 2 ), and the total length of the output grammar is also O(L 2 ).
To see the conversion algorithm in action, let’s apply these stages one at a time to our very
first example grammar for the language {0m 1n | m 6= n}:
S →A| BA → 0A | 0 C

B → B1 | C 1

C → " | 0C 1

0. Add a new starting non-terminal S 0 .
S0 → SS →A| BA → 0A | 0 C

B → B1 | C 1

C → " | 0C 1

1. Decompose the long production rule C → 0C 1.
S0 → SS →A| BA → 0A | 0C

B → B1 | C 1

C → " | 0D

D → C1

2. Identify C as the only nullable non-terminal. Because S 0 is not nullable, remove theproduction rule S 0 → S.
3. Eliminate the "-production C → ".
S →A| BA → 0A | 0 C | 0

B → B1 | C 1 | 1

C → 0D

D → C1 | 1

4. No two non-terminals are equivalent, so there’s nothing to merge.
5. Remove the unit productions S 0 → S, S → A, and S → B.
S → 0A | 0 C | B 1 | C 1 | 0 | 1
A → 0A | 0 C | 0

B → B1 | C 1 | 1

C → 0D

D → C 1 | 1.

6. Finally, protect the terminals 0 and 1 to obtain the final CNF grammar.
S → EA | EC | BF | C F | 0 | 1
A → EA | EC | 0

B → BF | C F | 1

C → ED

D → CF | 1

E→0

F →1
18

Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

Exercises
1. Describe context-free grammars that generate each of the following languages. The
function #(x, w) returns the number of occurrences of the substring x in the string w.
For example, #(0, 101001) = 3 and #(010, 1010100011) = 2. These are not listed inorder of increasing difficulty.
(a) All strings in {0, 1}∗ whose length is divisible by 5.
(b) All strings in {0, 1}∗ representing a non-negative multiple of 5 in binary.
(c) {w ∈ {0, 1}∗ | #(0, w) = 2 · #(1, w)}(d) {w ∈ {0, 1}∗ | #(0, w) 6= 2 · #(1, w)}(e) {w ∈ {0, 1}∗ | #(00, w) = #(11, w)}(f) {w ∈ {0, 1}∗ | #(01, w) = #(10, w)}(g) {w ∈ {0, 1}∗ | #(0, w) = #(1, w) and |w| is a multiple of 3}(h) {0, 1}∗ \ {0n 1n | n ≥ 0}(i) {0n 12n | n ≥ 0}(j) {0, 1}∗ \ {0n 12n | n ≥ 0}(k) {0n 1m | 0 ≤ 2m ≤ n < 3m}(l) {0i 1 j 2i+ j | i, j ≥ 0}(m) {0i 1 j 2k | i = j or j = k}(n) {0i 1 j 2k | i 6= j or j 6= k}(o) {0i 1 j 0 j 1i | i, j ≥ 0}(p) w#0#(0,w) w ∈ {0, 1}∗(q) {x y | x, y ∈ {0, 1}∗ and x 6= y and |x| = | y|}(r) x # y R x, y ∈ {0, 1}∗ and x 6= y(s) {x # y | x, y ∈ {0, 1}∗ and #(0, x) = #(1, y)}(t) {0, 1}∗ \ {ww | w ∈ {0, 1}∗ }(u) All strings in {0, 1}∗ that are not palindromes.
(v) All strings in {(, ), }∗ in which the parentheses are balanced and the symbol 
appears at most four times. For example, ()(()) and (   (()()  )()())  and   are strings in this language, but )(() and (    )   are not.
2. Describe recursive automata for each of the languages in problem 1. (“Describe” does notnecessarily mean “draw”!)
3. Prove that if L is a context-free language, then L R is also a context-free language. [Hint:
How do you reverse a context-free grammar?]
4. Consider a generalization of context-free grammars that allows any regular expression overΣ ∪ Γ to appear on the right side of a production rule. Without loss of generality, for each
non-terminal A ∈ Γ , the generalized grammar contains a single regular expression R(A). To
19

Models of Computation

Lecture 5: Context-Free Languages and Grammars [Sp’18]

apply a production rule to a string, we replace any non-terminal A with an arbitrary wordin the language described by R(A). As usual, the language of the generalized grammar isthe set of all strings that can be derived from its start non-terminal.
For example:, the following generalized context-free grammar describes the languageof all regular expressions over the alphabet {0, 1}:
S → (T +)∗ T + Ø(Regular expressions)

T →3+F F(Terms = summable expressions)

F → (0 + 1 + (S ))(* + ")(Factors = concatenable expressions)∗

Here is a parse tree for the regular expression 0+1(10*1+01*0)*10* (which represents
the set of all binary numbers divisible by 3):
S
T +

0

T
F

F

1 (

F

) * 1 0 *

S

+

T
F

F

F

1 0 * 1

F

T
F

F

F

0 1 * 0

Prove that every generalized context-free grammar describes a context-free language.
In other words, show that allowing regular expressions to appear in production rules does
not increase the expressive power of context-free grammars.

20