Problem Solving in Automata, Languages, and Complexity

112 CONTEXT-FREE LANGUAGES

scs

(a) If

5

a vertex

then we

ScSbS

abad, abSbScS abScScS

/

I I \ \

I \ \

1 .

abacSbS abacScS

Figure 3.5: Depth-first top-down search.

has two occurrences

delete this vertex.

of symbol b or two occurrences of symbol

Figure 3.5 shows the depth-first search tree of the graph g(G), with the
above pruning condition. Note that we stop the search as soon as the sentence
ubaca is found. The dot lines in Figure 3.5 denote the search paths that are
not yet performed.
We can also perform the graph search by a breadth-first search using the
same pruning criteria. We leave it as an exercise. cl

The above method applies only to context-free grammars G which have no
E-rules. What about grammars with E-rules? We note that there is a simple
method to find, from a grammar G, a new grammar G’ with no E-rule such
that L(G’) = L(G)-(E). N amely, we first identify all symbols that can derive
the empty string E. Then, for each such symbol A, we replace all rules of the

form I3 + uAv by B + uAv 1 UV, if uv # F. We also delete all rules of the

form A -+ E. It can be easily checked that this new grammar G’ generates all
strings in L(G) - {E}. Finally, if E E L(G), then we can first follow the above
step to eliminate all E-rules, and then add a new start symbol S’ and two new
rules S’ + S 1 E. The resulting grammar is then equivalent to G and has a
single E-rule S’ + E which does not affect our tree search algorithm.

Ambiguity. A context-free grammar G is ambiguous if there exists a string
x: f L(G) that has two different parse trees. Note that a parse tree for a
string x not only tells us whether x is in L(G), but also gives us the syntactic
structure of 8, which, in turn, may induce the semantic meaning of xx=. When x
has two parse trees, it makes it hard to determine which structure is the correct
one. Let us look at an example from a standard rule in many programming
languages.