Finite-State Machines and Pushdown Automata - Models of Computation: Exploring the Power of Computing - page 187

S

c c M N

b b

a a

N

M

a a c

M

c

Figure 4.28 A parse tree for the grammar G 3 .

associated with terminals and then traversing the remaining vertices in a depth-first manner
(visit the first descendant of a vertex before visiting its siblings), assuming that descendants of
a vertex are ordered from left to right. When a vertex is visited, apply the rule associated with
that vertex in the tree. The derivation given in ( 4.2 )isleftmost.
Not only can some strings in a context-free language have multiple derivations, but in
some languages they have multiple parse trees. Languages containing strings with more than
one parse tree are said to be ambiguous languages . Otherwise languages are non-ambiguous .
Given a string that is believed to be generated by a grammar, a compiler attempts to parse
the string after first scanning the input to identify letters. If the attempt fails, an error message
is produced. Given a string generated by a context-free grammar, can we guarantee that we can
always find a derivation or parse tree for that string or determine that none exists? The answer
is yes, as we now show.
TodemonstratethateveryCFLcanbeparsed,itisconvenientfirsttoconvertthegrammar
for such a language to Chomsky normal form.

DEFINITION 4.11.1 A context-free grammar G is in Chomsky normal form if every rule is of
the form A → BC or A → u , u ∈T except if ∈ L ( G ) , in which case S → is also in the

grammar.

We now give a procedure to convert an arbitrary context-free grammar to Chomsky normal
form.
THEOREM 4.11.1 Every context-free language can be generated by a grammar in Chomsky normal
form.
Proof Let L = L ( G ) where G is a context-free grammar. We construct a context-free gram-
mar G that is in Chomsky normal form. The process described in this proof is illustrated
by the example that follows.
Initially G is identical with G . We begin by eliminating all -rules of the form B → .

except for S → if ∈ L ( G ) .Ifeither B → or B ⇒ , for every rule that has B on the

) ∗ ( V = right-hand side, such as A → α B β B γ , α , β , γ ∈ ( V −{ } N∪T ), we add a rule

B

for each possible replacement of B by ; for example, we add A → αβ B γ , A → α B βγ ,