Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Theory of Computation
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/

Lecture 7: Further Properties of Context-Free Languages

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form I
As mentioned in the last lecture, context-free grammars are offundamental importance for programming languages.
However, in the specification of programming languages
usually a form different to the one provided in our Definition ofcontext-free grammars is used.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form I
As mentioned in the last lecture, context-free grammars are offundamental importance for programming languages.
However, in the specification of programming languages
usually a form different to the one provided in our Definition ofcontext-free grammars is used.
This form is the so-called Backus normal form or Backus-Naurform. It was created by John Backus to specify the grammar of
ALGOL. Later it has been simplified by Peter Naur to reducethe character set used and Donald Knuth proposed to call the
new form Backus-Naur form. Fortunately, whether or not one
is following Knuth’s suggestion, the form is commonly
abbreviated BNF.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form II

The form uses four meta characters that are not allowed toappear in the working vocabulary, i.e., in T ∪ N in our
definition. These meta characters are
h

i

::=

|

and the idea to use them is as follows. Strings (not containing
the meta characters) are enclosed by h and i denotenonterminals. The symbol ::= serves as a replacement operator(in the same way as → ) and | is read as “or.”Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form III
Example 1
Consider a context-free grammar for unsigned integers in a
programming language. Here, D stands for the class of digits
and U for the class of unsigned integers.
D → 0
D → 5

Theory of Computation

D

→

1

D

→

6

D

→

2

D

→

7

D

→

3

D

→

8

D

→

4

D

→

9

U

→

D

U

→

UD .

c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form III
Example 1
Consider a context-free grammar for unsigned integers in a
programming language. Here, D stands for the class of digits
and U for the class of unsigned integers.
D → 0
D → 5
D

→

1

D

→

6

D

→

2

D

→

7

D

→

3

D

→

8

D

→

4

D

→

9

U → D
Rewriting this example in BNF yields:

U

→

UD .

hdigiti ::= 0|1|2|3|4|5|6|7|8|9
hunsigned integeri ::= hdigiti|hunsigned integerihdigiti
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Backus-Naur Form IV

As this example clearly shows the BNF allows for a very
compact representation of the grammar. This is of particularimportance when defining the syntax of a programming
language, where the set of productions usually contains many
elements.
Whenever appropriate, we shall adopt a blend of the notation
used in BNFs, i.e., occasionally we shall use | as well as h and i
but not ::= .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Motivation
Context-free languages play an important role in many
applications. As far as regular languages are concerned, we
have seen that finite automata are very efficient recognizers.
So, what about context-free languages?

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Motivation
Context-free languages play an important role in many
applications. As far as regular languages are concerned, we
have seen that finite automata are very efficient recognizers.
So, what about context-free languages?
Again, for every context-free language a recognizer can bealgorithmically constructed. Formally, these recognizers are
pushdown automata. There are many software systems aroundthat perform the construction of the relevant pushdown
automaton for a given language. These systems are importantin that they allow the quick construction of the syntax analysis
part of a compiler for a new language and are therefore highly
valued.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Motivation
Context-free languages play an important role in many
applications. As far as regular languages are concerned, we
have seen that finite automata are very efficient recognizers.
So, what about context-free languages?
Again, for every context-free language a recognizer can bealgorithmically constructed. Formally, these recognizers are
pushdown automata. There are many software systems aroundthat perform the construction of the relevant pushdown
automaton for a given language. These systems are importantin that they allow the quick construction of the syntax analysis
part of a compiler for a new language and are therefore highly
valued.
We shall study them in Lectures 9 and 10.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Motivation
It is advantageous to treat another important tool for syntax
analysis first, i.e., parsers.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Motivation
It is advantageous to treat another important tool for syntax
analysis first, i.e., parsers.
One of the most widely used of these syntax analyzer
generators is called yacc (yet another compiler-compiler). The
generation of a parser, i.e., a function that creates parse trees
from source programs has been institutionalized in the yacc
command that appears in all UNIX systems. The input to yacc
is a CFG, in a notation that differs only in details from thewell-known BNF. Associated with each production is an action,
which is a fragment of C code that is performed whenever anode of the parse tree that (combined with its children)
corresponds to this production is created. So, let us continue
with parse trees.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees I

A nice feature of grammars is that they describe the hierarchicalsyntactic structure of the sentences of languages they define.
These hierarchical structures are described by parse trees.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees I

A nice feature of grammars is that they describe the hierarchicalsyntactic structure of the sentences of languages they define.
These hierarchical structures are described by parse trees.
Parse trees are a representation for derivations. When used in acompiler, it is the data structure of choice to represent thesource program. In a compiler, the tree structure of the source
program facilitates the translation of the source program into
executable code by allowing natural, recursive functions toperform this translation process.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees II
Parse trees are trees defined as follows.
Definition 1
Let G = [T , N, σ, P] be a context-free grammar. A parse tree for G
is a tree satisfying the following conditions.
(1) Each interior node and the root are labeled by a variablefrom N.
(2) Each leaf is either labeled by a non-terminal, a terminal or
the empty string. If the leaf is labeled by the empty string,then it must be the only child of its parent.
(3) If an interior node is labeled by h and its children arelabeled by x1 , . . . , xk , respectively, from left to right, thenh → x1 · · · xk is a production from P.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees III

Thus, every subtree of a parse tree describes one instance of an
abstraction in the statement. Next, we define the yield of aparse tree. If we look at the leaves of any parse tree andconcatenate them from left to right, we get a string. This stringis called the yield of the parse tree.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees III

Thus, every subtree of a parse tree describes one instance of an
abstraction in the statement. Next, we define the yield of aparse tree. If we look at the leaves of any parse tree andconcatenate them from left to right, we get a string. This stringis called the yield of the parse tree.
Clearly, of special importance is the case that the root is labeledby the start symbol and that the yield is a terminal string, i.e.,
all leaves are labeled with a symbol from T or the empty string.
Thus, the language of a grammar can also be expressed as theset of yields of those parse trees having the start symbol at theroot and a terminal string as yield.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees IV
Let us assume that we have the following part of a grammar on
hand that describes how assignment statements are generated.
Example 2

Theory of Computation

hassigni→

hidi := hexpri

hidi

→

A|B|C

hexpri→hidi + hexpri|

hidi ∗ hexpri|(hexpri)|hidi

c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees V
Now, let us look at the assignment statement A := B ∗ (A + C)
which can be generated by the following derivation.
hassigni

Theory of Computation⇒

hidi := hexpri⇒

A := hexpri⇒

A := hidi ∗ hexpri⇒

A := B ∗ hexpri⇒

A := B ∗ (hexpri)⇒

A := B ∗ (hidi + hexpri)⇒

A := B ∗ (A + hexpri)⇒

A := B ∗ (A + hidi)⇒

A := B ∗ (A + C)

c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees V
The structure of the assignment statement that we have justderived is shown in the parse tree displayed below.
<assign>
<id>

A

:=

<expr><id> *<expr>

B

(

<expr

)

<id>

+

<expr>A<id>

C

Figure 1: Parse tree for sentence A := B ∗ (A + C)

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees VI
Note that syntax analyzers for programming languages, which
are often called parsers, construct parse trees for given
programs. Some systems construct parse trees only implicitly,
but they also use the whole information provided by the parsetree during the parse. There are two major approaches of how
to build these parse trees. One is top-down and the other one isbottom-up. In the top-down approach the parse tree is built
from the root to the leaves while in the bottom-up approach theparse tree is built from the leaves upward to the root.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Parse Trees VI
Note that syntax analyzers for programming languages, which
are often called parsers, construct parse trees for given
programs. Some systems construct parse trees only implicitly,
but they also use the whole information provided by the parsetree during the parse. There are two major approaches of how
to build these parse trees. One is top-down and the other one isbottom-up. In the top-down approach the parse tree is built
from the root to the leaves while in the bottom-up approach theparse tree is built from the leaves upward to the root.
A major problem one has to handle when constructing suchparsers is ambiguity. We thus direct our attention to thisproblem.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity I
Definition 2
A grammar that generates a sentence for which there are two or
more distinct parse trees is said to be ambiguous.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity I
Definition 2
A grammar that generates a sentence for which there are two or
more distinct parse trees is said to be ambiguous.
For having an example, let us look at the following part of agrammar given in Example 3. At first glance this grammar
looks quite similar to the one considered above. The only
difference is that the production for expressions has beenaltered by replacing hidi by hexpri.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity I
Definition 2
A grammar that generates a sentence for which there are two or
more distinct parse trees is said to be ambiguous.
For having an example, let us look at the following part of agrammar given in Example 3. At first glance this grammar
looks quite similar to the one considered above. The only
difference is that the production for expressions has beenaltered by replacing hidi by hexpri.
However, this small modification leads to serious problems,
because now the grammar provides slightly less syntactic
structure than the grammar considered in Example 2 does.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity II
Example 3
hassigni→

hidi := hexpri

hidi

→

A|B|C

hexpri→hexpri + hexpri|

hexpri ∗ hexpri|(hexpri)|hidi

For seeing that this grammar is ambiguous, let us look at thefollowing assignment statement:
A := B + C ∗ A .
We skip the two formal derivations possible for thisassignment and look directly at the two parse trees.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity III<assign><id><assign>:=A<expr><expr> +<id> <expr>

B

<id>

<expr>*<expr> *A<expr>

<id>

<id>

C

A

<expr>:=<expr>+<expr><expr> <id>

<id>

<id>

B

C

A

Figure 2: Two parse trees for the same sentence A := B + C ∗ A

A := B + (C ∗ A)
Theory of Computation

A := (B + C) ∗ A.
c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity IV
These two distinct parse trees cause problems because
compilers base the semantics of the sentences on their syntactic
structure. In particular, compilers decide what code to generateby examining the parse tree. So, in our example the semantics is
not clear. Let us examine this problem in some more detail.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity IV
These two distinct parse trees cause problems because
compilers base the semantics of the sentences on their syntactic
structure. In particular, compilers decide what code to generateby examining the parse tree. So, in our example the semantics is
not clear. Let us examine this problem in some more detail.
In the first parse tree (the left one) of Figure 2 the multiplication
operator is generated lower in the tree which would indicatethat it has precedence over the addition operator in theexpression.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity IV
These two distinct parse trees cause problems because
compilers base the semantics of the sentences on their syntactic
structure. In particular, compilers decide what code to generateby examining the parse tree. So, in our example the semantics is
not clear. Let us examine this problem in some more detail.
In the first parse tree (the left one) of Figure 2 the multiplication
operator is generated lower in the tree which would indicatethat it has precedence over the addition operator in theexpression.
The second parse tree in Figure 2, however, is just indicating the
opposite. Clearly, in dependence on what decision the compiler
makes, the result of an actual evaluation of the assignment
given will be either the expected one (that is multiplication has
precedence over addition) or an erroneous one.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity V
Although the grammar in Example 2 is not ambiguous, theprecedence order of its operators is not the usual one. Rather, in
this grammar, a parse tree of a sentence with multiple operators
has the rightmost operator at the lowest point, with the otheroperators in the tree moving progressively higher as one moves
to the left in the expression.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity V
Although the grammar in Example 2 is not ambiguous, theprecedence order of its operators is not the usual one. Rather, in
this grammar, a parse tree of a sentence with multiple operators
has the rightmost operator at the lowest point, with the otheroperators in the tree moving progressively higher as one moves
to the left in the expression.
So, one has to think about a way to overcome this difficulty andto clearly define the usual operator precedence between
multiplication and addition, or more generally with any
desired operator precedence. As a matter of fact, this goal canbe achieved for our example by using separate nonterminals forthe operands of the operators that have different precedence.
This not only requires additional nonterminals but also
additional productions.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VI
Question
Can we always detect ambiguity?
If ambiguity has been detected, can it always be removed?

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VI
Question
Can we always detect ambiguity?
If ambiguity has been detected, can it always be removed?

The answers are given by the following theorems.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VI
Question
Can we always detect ambiguity?
If ambiguity has been detected, can it always be removed?

The answers are given by the following theorems.
Theorem 1
There is no algorithm deciding whether or not any context-freegrammar is ambiguous.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VI
Question
Can we always detect ambiguity?
If ambiguity has been detected, can it always be removed?

The answers are given by the following theorems.
Theorem 1
There is no algorithm deciding whether or not any context-freegrammar is ambiguous.
Theorem 2
There are context-free languages that have nothing but ambiguous
grammars.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VII

But in practice the situation is not as grim as it may seem.
Many techniques have been proposed to eliminate ambiguity inthe sorts of constructs that typically appear in programming
languages.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VII

But in practice the situation is not as grim as it may seem.
Many techniques have been proposed to eliminate ambiguity inthe sorts of constructs that typically appear in programming
languages.
So, let us come back to our example and let us show how toeliminate the ambiguity we have detected. We continue by
providing a grammar generating the same language as thegrammars of Examples 2 and 3, but which clearly indicates theusual precedence order of multiplication and addition.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VIII
Example 4hassigni→

hidi := hexpri

hidi

→

A|B|C

hexpri→hexpri + htermi|

htermi→htermi ∗ hfactori|

hfactori→(hexpri)|hidi

htermihfactori

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity VIII
Example 4hassigni→

hidi := hexpri

hidi

→

A|B|C

hexpri→hexpri + htermi|

htermi→htermi ∗ hfactori|

hfactori→(hexpri)|hidi

htermihfactori

Next, let us derive the same statement as above, i.e.,
A := B + C ∗ A .
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity IX
The derivation is unambiguously obtained as follows:
hassigni

Theory of Computation⇒

hidi := hexpri ⇒ A := hexpri⇒

A := hexpri + htermi⇒

A := htermi + htermi⇒

A := hfactori + htermi⇒

A := hidi + htermi⇒

A := B + htermi⇒

A := B + htermi ∗ hfactori⇒

A := B + hfactori ∗ hfactori⇒

A := B + hidi ∗ hfactori⇒

A := B + C ∗ hfactori⇒

A := B + C ∗ hidi⇒

A := B + C ∗ A
c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity X
Furthermore, you should note that we have presented a leftmost
derivation above, i.e., the leftmost nonterminal has always beenhandled first until it was replaced by a terminal. Thus, thesentence given above has more than one derivation. If we had
always handled the rightmost nonterminal first, then we would
have been arrived at a rightmost derivation.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity X
Furthermore, you should note that we have presented a leftmost
derivation above, i.e., the leftmost nonterminal has always beenhandled first until it was replaced by a terminal. Thus, thesentence given above has more than one derivation. If we had
always handled the rightmost nonterminal first, then we would
have been arrived at a rightmost derivation.
Clearly, one could also choose arbitrarily the nonterminal
which allows the application of a production. Try it out, andconstruct the resulting parse trees. Usually, one is implicitly
assuming that derivations are leftmost. Thus, we can more
precisely say that a context-free grammar is ambiguous if there isa sentence in the language it generates that possesses at least
two different leftmost derivations. Otherwise it is called
unambiguous. A language is said to be unambiguous if there isan unambiguous grammar for it.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity XI
Another important problem in describing programming
languages is to express that operators are associative. As you
have learned in mathematics, addition and multiplication areassociative. Is this also true for computer arithmetic? As far asinteger addition and multiplication are concerned, they areassociative. But floating point computer arithmetic is notalways associative. So, in general correct associativity isessential. The book provides more information.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity XI
Another important problem in describing programming
languages is to express that operators are associative. As you
have learned in mathematics, addition and multiplication areassociative. Is this also true for computer arithmetic? As far asinteger addition and multiplication are concerned, they areassociative. But floating point computer arithmetic is notalways associative. So, in general correct associativity isessential. The book provides more information.
As an exercise you should try to provide an unambiguous
grammar for the if-then-else statement that is present in many
programming languages.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Ambiguity XI
Another important problem in describing programming
languages is to express that operators are associative. As you
have learned in mathematics, addition and multiplication areassociative. Is this also true for computer arithmetic? As far asinteger addition and multiplication are concerned, they areassociative. But floating point computer arithmetic is notalways associative. So, in general correct associativity isessential. The book provides more information.
As an exercise you should try to provide an unambiguous
grammar for the if-then-else statement that is present in many
programming languages.
We continue with further properties of context-free grammars.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars I
In a context-free grammar, there is no a priori bound on the sizeof a right-hand side of a production. This may complicate
many proofs. But, there is a normal form for context-free grammars
bounding the right-hand side to be of length at most 2.
Knowing and applying this considerably simplifies many
proofs.
First, we define the notion of a separated grammar.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars I
In a context-free grammar, there is no a priori bound on the sizeof a right-hand side of a production. This may complicate
many proofs. But, there is a normal form for context-free grammars
bounding the right-hand side to be of length at most 2.
Knowing and applying this considerably simplifies many
proofs.
First, we define the notion of a separated grammar.
Definition 3
A grammar G = [T , N, σ, P] is called separated if for all(α → β) ∈ P we either have α, β ∈ N∗ or α ∈ N and β ∈ T .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars I
In a context-free grammar, there is no a priori bound on the sizeof a right-hand side of a production. This may complicate
many proofs. But, there is a normal form for context-free grammars
bounding the right-hand side to be of length at most 2.
Knowing and applying this considerably simplifies many
proofs.
First, we define the notion of a separated grammar.
Definition 3
A grammar G = [T , N, σ, P] is called separated if for all(α → β) ∈ P we either have α, β ∈ N∗ or α ∈ N and β ∈ T .
Theorem 3
For every context-free grammar G = [T , N, σ, P] there exists anequivalent separated context-free grammar G 0 = [T , N 0 , σ, P 0 ].
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars II

Proof. First, we introduce for every t ∈ T a new nonterminal
symbol ht , where by new we mean that ht < N for all t ∈ T .
Furthermore, we set N 0 = {ht | t ∈ T } ∪ N.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars II

Proof. First, we introduce for every t ∈ T a new nonterminal
symbol ht , where by new we mean that ht < N for all t ∈ T .
Furthermore, we set N 0 = {ht | t ∈ T } ∪ N.
Next, for (α → β) ∈ P, we denote the production obtained byreplacing every terminal symbol t in β by ht by(α → β)[t//ht ]. The production set P 0 is then defined asfollows.
P 0 = {(α → β)[t//ht ] | (α → β) ∈ P} ∪ {ht → t | t ∈ T } .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars II

Proof. First, we introduce for every t ∈ T a new nonterminal
symbol ht , where by new we mean that ht < N for all t ∈ T .
Furthermore, we set N 0 = {ht | t ∈ T } ∪ N.
Next, for (α → β) ∈ P, we denote the production obtained byreplacing every terminal symbol t in β by ht by(α → β)[t//ht ]. The production set P 0 is then defined asfollows.
P 0 = {(α → β)[t//ht ] | (α → β) ∈ P} ∪ {ht → t | t ∈ T } .
By construction, we directly see that G 0 is separated.
Moreover, the construction ensures that G 0 is context-free, too.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars III
It remains to show that L(G) = L(G 0 ).
Claim 1. L(G) ⊆ L(G 0 ).
Let s ∈ L(G). Then there exists a derivation
1

1

1

1

1

σ ⇒ w1 ⇒ w2 ⇒ · · · ⇒ wn ⇒ s ,where w1 , . . . , wn ∈ (N ∪ T )+ \ T ∗ , and s ∈ T ∗ . Let Pi be theproduction used to generate wi , i = 1, . . . , n.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars III
It remains to show that L(G) = L(G 0 ).
Claim 1. L(G) ⊆ L(G 0 ).
Let s ∈ L(G). Then there exists a derivation
1

1

1

1

1

σ ⇒ w1 ⇒ w2 ⇒ · · · ⇒ wn ⇒ s ,where w1 , . . . , wn ∈ (N ∪ T )+ \ T ∗ , and s ∈ T ∗ . Let Pi be theproduction used to generate wi , i = 1, . . . , n.
Then we can generate s by using productions from P 0 as
follows. Let s = s1 · · · sm , where sj ∈ T for all j = 1, . . . , m.
Instead of applying Pi we use Pi [t//ht ] from P 0 and obtain
1

1

1

1

1

0
σ ⇒ w10 ⇒ w20 ⇒ · · · ⇒ wn
⇒ hs1 · · · hsm ,where now wi0 ∈ (N 0 )+ for all i = 1, . . . , n.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars III
It remains to show that L(G) = L(G 0 ).
Claim 1. L(G) ⊆ L(G 0 ).
Let s ∈ L(G). Then there exists a derivation
1

1

1

1

1

σ ⇒ w1 ⇒ w2 ⇒ · · · ⇒ wn ⇒ s ,where w1 , . . . , wn ∈ (N ∪ T )+ \ T ∗ , and s ∈ T ∗ . Let Pi be theproduction used to generate wi , i = 1, . . . , n.
Then we can generate s by using productions from P 0 as
follows. Let s = s1 · · · sm , where sj ∈ T for all j = 1, . . . , m.
Instead of applying Pi we use Pi [t//ht ] from P 0 and obtain
1

1

1

1

1

0
σ ⇒ w10 ⇒ w20 ⇒ · · · ⇒ wn
⇒ hs1 · · · hsm ,where now wi0 ∈ (N 0 )+ for all i = 1, . . . , n. Thus, in order toobtain s it now suffices to apply the productions hsj → sj for
j = 1, . . . m. This proves Claim 1.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Separated Grammars IV

Claim 2. L(G 0 ) ⊆ L(G).
This claim can be proved analogously by inverting theconstruction used in showing Claim 1.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form I
Now, we are ready to define the normal form for context-freegrammars announced above.
Definition 4
A grammar G = [T , N, σ, P] is said to be in Chomsky normal
form if all productions of P have the form h → h1 h2 , whereh, h1 , h2 ∈ N, or h → x, where h ∈ N and x ∈ T .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form I
Now, we are ready to define the normal form for context-freegrammars announced above.
Definition 4
A grammar G = [T , N, σ, P] is said to be in Chomsky normal
form if all productions of P have the form h → h1 h2 , whereh, h1 , h2 ∈ N, or h → x, where h ∈ N and x ∈ T .
The latter definition directly allows the following corollary.
Corollary 4
Let G = [T , N, σ, P] be a grammar in Chomsky normal form. Then
(1) G is context-free,(2) G is λ-free,(3) G is separated.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form II

Now, we can show:
Theorem 5
For every context-free grammar G = [T , N, σ, P] such that λ < L(G)there exists an equivalent grammar G 0 that is in Chomsky normal
form.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form II

Now, we can show:
Theorem 5
For every context-free grammar G = [T , N, σ, P] such that λ < L(G)there exists an equivalent grammar G 0 that is in Chomsky normal
form.
Proof. Let G = [T , N, σ, P] be given. Without loss of generality,
we may assume that G is reduced.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form III
First, we eliminate all productions of the form h → h 0 . This isdone as follows. We set
W0 (h) = {h} for every h ∈ N
and for each i > 0 we define
Wi+1 (h) = Wi (h)∪{h̃ | h̃ ∈ N, (ĥ → h̃) ∈ P for some ĥ ∈ Wi (h)} .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form III
First, we eliminate all productions of the form h → h 0 . This isdone as follows. We set
W0 (h) = {h} for every h ∈ N
and for each i > 0 we define
Wi+1 (h) = Wi (h)∪{h̃ | h̃ ∈ N, (ĥ → h̃) ∈ P for some ĥ ∈ Wi (h)} .
Then, the following facts are obvious:(1) Wi (h) ⊆ Wi+1 (h)for all i > 0,(2) If Wi (h) = Wi+1 (h) then Wi (h) = Wi+m (h) for all m ∈ N,
(3) Wn (h) = Wn+1 (h) for n = card(N),∗(4) Wn (h) = {B | B ∈ N and h ⇒ B}.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form IV
Now, we define
P1 = {h → γ | h ∈ N, γ < N, (B → γ) ∈ P
for some B ∈ Wn (h)} .
Let G1 = [T , N, σ, P1 ],Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form IV
Now, we define
P1 = {h → γ | h ∈ N, γ < N, (B → γ) ∈ P
for some B ∈ Wn (h)} .
Let G1 = [T , N, σ, P1 ], then by construction P1 does not containany production of the form h → h 0 . These productions have∗been replaced by h → γ. That is, if we had h ⇒ B by using the
productions from P and B → γ, then we now have theproduction h → γ in P1 . Also note that P1 contains all original
productions (h → γ) ∈ P, where γ < N by the definition of W0 .
We leave it as an exercise to formally verify that L(G1 ) = L(G).

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form V
Next, from G1 we construct an equivalent separated grammar
G2 by using the algorithm given above. Now, the only
productions in P2 that still need modification are of the formh → h1 h2 · · · hn , where n > 3 .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form V
Next, from G1 we construct an equivalent separated grammar
G2 by using the algorithm given above. Now, the only
productions in P2 that still need modification are of the formh → h1 h2 · · · hn , where n > 3 .
We replace any such production by the following productionsh→h1 hh2 ···hn

hh2 ···hn→

h2 hh3 ···hn→

hn−1 hn···
hhn−1 hn

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Chomsky Normal Form V
Next, from G1 we construct an equivalent separated grammar
G2 by using the algorithm given above. Now, the only
productions in P2 that still need modification are of the formh → h1 h2 · · · hn , where n > 3 .
We replace any such production by the following productionsh→h1 hh2 ···hn

hh2 ···hn→

h2 hh3 ···hn→

hn−1 hn···
hhn−1 hnHence, the resulting grammar G 0 is in Chomsky normal formand by construction equivalent to G. We omit the details.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma I

We finish this lecture by pointing to an important result which
can be proved by using the Chomsky normal form. This result
is usually referred to as Pumping Lemma for context-freelanguages or Lemma of Bar-Hillel or qrsuv-Theorem.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma I

We finish this lecture by pointing to an important result which
can be proved by using the Chomsky normal form. This result
is usually referred to as Pumping Lemma for context-freelanguages or Lemma of Bar-Hillel or qrsuv-Theorem.
Please note that the qrsuv-Theorem provides a necessary
condition for a language to be context-free. It is not sufficient.
So its main importance lies in the fact that one can often use it
to show that a language is not context-free.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma II
Theorem 6 (qrsuv-Theorem, Pumping Lemma)
For every context-free language L there is a number k such that forevery w ∈ L with |w| > k there are strings q, r, s, u, v such that(1) w = qrsuv,(2) |rsu| 6 k,(3) ru , λ, and(4) qri sui v ∈ L

Theory of Computation

for all i ∈ N.

c Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma II
Theorem 6 (qrsuv-Theorem, Pumping Lemma)
For every context-free language L there is a number k such that forevery w ∈ L with |w| > k there are strings q, r, s, u, v such that(1) w = qrsuv,(2) |rsu| 6 k,(3) ru , λ, and(4) qri sui v ∈ L

for all i ∈ N.

Proof. Let G = [T , N, σ, P] be any context-free grammar in CNF
for L. Then all parse trees are binary trees except the lastderivation step.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma III
Let n = card(N) and k = 2n and consider the parse tree for any
string w ∈ L(G) with |w| > k. So, any of the parse trees for w
must have depth at least n. Hence, there must exist a path fromthe root σ to a leaf having length at least n. Including σ there
are n + 1 nonterminals on this path. Hence, some nonterminal hhas to appear at least twice (see Figure 3, Part (a)).
σ

σ

h

h
h

|

last derivation
step

{z

h
}

q

r

s u

v

w

Part (a)Part (b)Figure 3: Parse trees for illustrating the proof of the qrsuv-Theorem
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma IV

Now, starting from the leaves and going up, we fix a pathcontaining two times h and we fix the first two occurrences ofh. In this way, we guarantee that the higher located occurrenceof h is at most n steps above the leaves.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma IV

Now, starting from the leaves and going up, we fix a pathcontaining two times h and we fix the first two occurrences ofh. In this way, we guarantee that the higher located occurrenceof h is at most n steps above the leaves.
Next, we look at the substrings that are generated from these
two occurrences of h. This gives us the substrings qrsuv (seeFigure 3, Part (b)).

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma IV

Now, starting from the leaves and going up, we fix a pathcontaining two times h and we fix the first two occurrences ofh. In this way, we guarantee that the higher located occurrenceof h is at most n steps above the leaves.
Next, we look at the substrings that are generated from these
two occurrences of h. This gives us the substrings qrsuv (seeFigure 3, Part (b)).
Because G is in CNF, at the higher occurrence of h a productionof the form h → h1 h2 must have been applied. Consequently,
r , λ or u , λ, and Assertion (3) is shown.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma V

Assertion (2) follows from the fact that the higher locatedoccurrence of h is at most n steps above the leaves. Thus, thestring rsu derived from this h can have length at most 2n = k.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma V

Assertion (2) follows from the fact that the higher locatedoccurrence of h is at most n steps above the leaves. Thus, thestring rsu derived from this h can have length at most 2n = k.
It remains to show Assertion (4). This is done by modifying theparse tree. First, we may remove the subtree rooted at thehigher located occurrence of h and replace it by the subtree
rooted at the lower located occurrence of h (see Figure 4,
Part (a)). In this way, we get a generation of qsv, i.e.,
qr0 su0 v ∈ L(G).

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma VI

σ

σ

h

h

s

h

q

v

q

r

u

v

h

Part (a)r s uPart (b)Figure 4: Illustrating Assertion (4) of the qrsuv-Theorem

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma VII

Second, we remove the subtree rooted at the lower locatedoccurrence of h and replace it by the subtree rooted at thehigher located occurrence of h (see Figure 4, Part (b)). In thisway, we get a derivation of qr2 su2 v and thus, qr2 su2 v ∈ L(G).
Iterating this idea shows qri sui v ∈ L(G) for every i ∈ N+ .

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma VII

Second, we remove the subtree rooted at the lower locatedoccurrence of h and replace it by the subtree rooted at thehigher located occurrence of h (see Figure 4, Part (b)). In thisway, we get a derivation of qr2 su2 v and thus, qr2 su2 v ∈ L(G).
Iterating this idea shows qri sui v ∈ L(G) for every i ∈ N+ .
For having an application of Theorem 6, we show the following
Theorem, thus completing the proof of Theorem 6.5.

Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Pumping Lemma VIII
Theorem 7
L = {an bn cn | n ∈ N} < CF.
Proof. Suppose the converse. Then, by Theorem 6 there is a ksuch that for all w ∈ L with |w| > k we have:
There are substrings q, r, s, u, v with |ru| > 0 and for all
w = qrsuv ∈ L we must have qri sui v ∈ L, too, for all i ∈ N.
Now, consider w = ak bk ck . Consequently, |w| = 3k > k. By
Assertion (2) of Theorem 6 we have |rsu| 6 k, and thus ru
cannot contain a’s, b’s and c’s. Since |ru| > 0 and byAssertion (4) (applied for i = 0), we must have
qr0 su0 v = qsv ∈ L. But, as discussed above, qsv , a` b` c` forevery ` ∈ N, a contradiction.
Theory of Computationc Thomas Zeugmann

Backus-Naur Form

Parse Trees, Ambiguity

Chomsky Normal Form

Pumping Lemma

End

Thank you!

Theory of Computationc Thomas Zeugmann