Context-free grammars can be badly
designed. For example they can have
variables that play no role in the
derivation of any terminal string and
therefore shouldn't be there. As analogous
to states in the [inaudible] an automaton
that aren't reachable from the start
state. There are also certain productions
that, while they are necessary, cause
derivations to take many steps that can
obviously be combined. These include
productions whose bodies are the empty
string or unit productions where the body
is a single variable. We can get rid of
these and the way to do so is similar to
the way we removed epsilon transitions
from an NFA. Finally, we're going to
introduce [inaudible] normal form where
all the production bodies are either a
single terminal or two variables.
Incidentally, the Chomsky we refer to is
Noam Chomsky. Back in 1956, he wrote the
paper that introduced the idea of
context-free grammars. Then he was a
linguist trying to provide some
mathematics for the structure of the
language. Since then he has unfortunately
became somewhat notorious for his
political views. Oh well, back to
context-free grammars. Here is an example
of a really bad grammar. A is okay, it
derives all strings of one or more A's
using its two productions. However B has
only one production and that production
has B in its body. Thus, once it's
sentential form has a B in it, you can
never get rid of that B. And as a result,
B derives no terminal strings. To make
matters worse, S is only one production.
So that must be the first used than any
derivation. But that production introduces
a B into the cententional form so it is
impossible to derive any terminal string
from S and therefore the language of this
grammar is empty. Almost all the
algorithms we need to simplify grammars
are based on the same principle, which I
call discovery algorithms. These discover
facts by an induction process The basis is
always certain facts that are obvious.
Then based on what is already known, we
discover facts and repeated rounds.
Finally, at some round, they can discover
no more facts. There's no point in going
on since without new facts in the current
round, we cannot discover more on the next
round. We generally have to prove only
that any true fact of the type we are
trying to discover will be found this way.
Here's the image of discovery algorithms
we should keep in mind. We start with some
facts you get from the basis. We expand
the set of facts you know by using the
basis fact, this is the first round. For
the second round, we expand the set of
known facts further by using both the
basic facts and the facts you discovered
around one. You keep going until some
round you have no more facts that can be
discovered. So one of the first things we
need to do when dealing with grammars is
to detect and get rid of variables that
can't derive any terminal string. We shall
give a discovery algorithm to find
inductively, all variables that do derive
at least one terminal string, any variable
not discovered by this algorithm derives
no terminal strings and can be eliminated.
For the basis of a variable A has a
production who's body has no variables,
then A certainly derives a terminal string
in one step. Note that this body could be
the empty string, technically string is a
string of terminals. Now suppose A has
production with a body alpha and alpha
consists of only terminals and variables
that we have previously discovered derives
from terminal string and A derives from
terminal string. Since the number of
variables is finite eventually this
algorithm terminates where it can't find
no more variables that derive terminal
strings. Its is easy to prove that
whenever the algorithm says a variable
derives a terminal string that it really
does derive a terminal string, we are not
going to prove that. The harder part is
showing that the algorithm doesn't miss
anything, that is if variable A derives
some terminal string, then the algorithm
will eventually discover A, we will do
that on the next slide. The proof is in
the induction of the minimum height of a
parse tree with root A and a yield of
terminals. The basis is a tree of height
one which consists of root A and one or
more leaves labeled by terminals or
perhaps epsilon. Then the basis step of
the algorithm discovers A, so we are okay
there. For the induction, assume the
statement is true for height up to H-1,
that is all variables at are the roots of
parse trees with a height up to H-1 and a
yield of terminals that are discovered by
the algorithm. The parse tree for height
H, which must be of course equal to or
greater than two, has children of the root
labeled X1 through Xn, that's this. Anyone
of these Xi's that is a variable is the
root of the sub tree of height at most H-1
and therefore it is discovered. Moreover,
one of these variables is discovered last.
At the round, with the last of the
variables AIs is discovered, we must
surely do another round since the set of
discovered variables just changed. On the
next round, A will be discovered because
it has a production, that is A goes to
X1through XN. Who's body consists of only
bodies and discovered variables. The
algorithms do eliminate variables that
derive no terminal string is no-, simple.
Use the algorithm that we just described
to find the variables that do derive
terminal strings. Call the other variables
useless. Then remove from the grammar all
productions in which in least one useless
variable appears. It doesn't matter if the
variable appears in the head, the body or
both. Here's an example grammar to which
we first apply the algorithm that derive
terminal strings. For the basis step, we
immediately discover A and C because they
have productions with terminals only. Here
they are. For the first round of the
production, S is discovered because there
is a S production with body C. And C was
previously discovered. However at the next
round we can discover no more variables.
The only variable we have not yet found to
derive a terminal string is B and B has
only one production body which is little B
followed by big B. This body does not
exist only of terminals and discovered
variables so we can never add B to the set
of discovered variables. Unless B is
useless and we eliminate all traces of it.
That includes not only the production B
goes to but the production S goes to AB,
leaving us of course, fortunately, S goes
to C, still remains as well as the 2A
production and the C production. In
addition to eliminating the variables that
don't derive anything, we need to
eliminate variables that derive some
terminal strings but cannot be derived
from the start symbol. The algorithm to
define symbols both terminals and
variables that appear in variation from
the start symbol is a derivation of the
discovery algorithm. For the basis,
obviously the start symbol can be derived
from zero steps from itself. For the
induction, suppose we have discovered that
we can reach variable A and then for every
production with body alpha and head A, we
can also redraw the symbols appearing in
alpha. The terminals and variables that
appear there. It is an easy pair of
inductions to show, first that if we
discover an a symbol by this algorithm,
that it appears in the sentential form
derived from the start symbol. Second,
that if we do not discover a symbol, then
there is no derivation from the start
symbol from which it appears, we are not
going to give the proofs here. But
remember our goal is to get rid of that do
not appear on the derivations from S. So
after discovering all the symbols that do
appear in a derivation, delete from the
grammar all the productions that contain a
symbol, and now that head or body or both,
that does not appear in a derivation. Say
a symbol is useful if it appears in a
derivation of a terminal string from the
start symbol. And call it useless
otherwise. There are two reasons a symbol
can be useless, either it derives no
terminal string or it appears in no
derivation from the start symbol, or both.
We have algorithms to eliminate symbols
that are useless fro each of the reasons
but we must apply them in the right order.
First eliminate the symbols that fail to
derive a terminal string. And then
eliminate symbols that do not appear from
any derivation from the start symbol. In
this example grammar, if as we should, we
first eliminate variables that do not
derive a terminal string. We eliminate
only B, however eliminating productions
with B gets rids of the only S production.
We then use the algorithm to find symbol
unreachable from the start symbol and we
find that everything is unreachable, that
is all the productions are deleted.
However, if we do things in the wrong
order and first eliminate unreachable
symbols, we find everything is reachable
from S so nothing is eliminated here. Then
when we look from the symbols that do not
derive terminal strings, we eliminate only
B. That leaves the productions A and C
goes to little c, these guys, which should
not be there because A, C and little c are
useless. Here's why first eliminating
variables that don't derive terminal
strings is the right thing to do. After
eliminating those variables, every
remaining symbol is either a terminal or
is a variable that derives a terminal
string. After removing symbols not
reachable form the start symbol, all
remaining symbols appear in some
derivation from the start symbol of some
sentential form. But the variables that
appear in sentential form still derive at
terminal string because such a derivation
can only involve symbols that are also
reachable from the start symbol. Epsilon
productions are those that have body
epsilon, they can be eliminated from a
context free grammar and the only thing
that we lose is that we can no longer
derive the empty string. If the empty
stream was not on the language to begin
with, then we can eliminate epsilon
productions and still have a grammar that
derives the same language. However, if
epsilon was in the language then we lose
it, the two cases can be summarized by the
theorem on the slide, if L has the
grammar. Then L minus the set containing
the empty string has a grammar with no
epsilon productions. Notice that if an
epsilon was not an L then L minus epsilon
is just L anyway. To eliminate epsilon
productions, we need yet another discovery
algorithm, this one to find the variables
that derive the empty string by one or
more steps. We call them null-able
symbols. The basis of the discovery
algorithm is that if A has a production
with an empty body then it is surely
nullable. And the inductions is that if A
has a production with body alpha and alpha
consists only of variables that are
nullable then A is also nullable. Here is
an example grammar for which we will
discover the nullable symbols. The basis
we know that A is nullable because of the
production with epsilon body, its that. In
the first round of the induction we find B
is nullabe because of the production B
goes to A. That is all symbols on the
body, namely the A, are already known to
be nullable. In the second round of the
basis we discover that S is nullable
because of it's body AB, both symbols of
which are already known to be nullable.
This algorithm finds all and only the
nullable symbols. We are not going to give
the proof, which consists of two simple
inductions. To eliminate epsilon
productions from our grammar we need to we
need to turn each production, say A goes
to epsilon through Xn, into a possibly
large number of productions. The idea is
to guess which of the nullable symbols of
the body of a production will derive
epsilon in a particular derivation, since
we make all possible guess by creating
many different many productions, we always
manage to guess right. More precisely, for
each set of nullable Xis. These from the
body of the production make a new A
production. Note, that if two of the Xi's
are the same nullable symbol then we have
to consider the possibility that one
[inaudible] derives epsilon and the other
does not. That is we form one production
for each set of positions that hold
nullable symbols, not just for each set of
nullable symbols. However in the special
case that all the Xi's are nullable
symbols, we do not consider the set of all
positions and we do not create a new
production with the epsilon body. Here is
an example grammar. Each of A, B, and C
are nullable because they have epsilon
productions. Thus, S is also nullable
because of it's production S goes to A, B,
C. Lets construct the new grammar. For the
S production there are seven sub sets of
nullable positions that we must use. The
set of all three positions is also
nullable of course, but eliminating all of
A, B, C would leave an empty body which we
don't allow. However if we use the empty
set positions we get body A, B, C. If we
use the set of only the third position, we
get AB, and so on. Now lets look at the A
productions. We do not use A goes to
epsilon of course, but for production A
goes to little A big A, its that. Only the
second position is nullable so we get two
productions, one with the variable A
present and the other not, that is what we
have here. The situation for B is the
same. However C we, for C we cannot use
the C goes to epsilon production. So in
the new grammar, C has no production. That
means that in the new grammar, although
not in the old grammar, C is useless and
must be eliminated. That forces us to
eliminate all productions with C in the
body. And we are done. The proof that the
new grammar we construct generates the
same strings except for epsilon as the old
grammar generates is a little tricky. So
we're going to give the details in one
direction. As is often the case, we need
to prove something more general than we
really need. In this case, we need two
statements about every variable A. First,
if W is a non-empty string that is derived
from A in the old grammar, then A also
derives W in the newly constructed
grammar. Second, if A derives W in the new
grammar, first of all W is not empty and
second A derives W in the old grammar.
Once we have that for all A we can apply
the statement to the start symbol and thus
prove that the language of the new grammar
is the language of the old grammar with
epsilon removed if it was in that
language. We're going to prove the first
direction and it is an induction on the
number of steps by which A derives W in
the old grammar. For the basis, if there's
a one step derivation of W from A then A
goes to W must be a production. We assume
in part one that W's not empty, so A goes
to W is a production of the new grammar.
You make a desired conclusion that A
derives W in the new grammar. Now let's do
the induction. Assume the inductive
hypothesis for derivations at fewer than K
steps and suppose W is derived from A in K
steps of the old grammar. The first step
of this derivation must be A replaced by
the body of some A production. Assume this
body consists of symbols X1 through Xn.
Then we can break W into W1 through Wn
where each WI is the portion of W that
either is XI if XI is a terminal or it's
derived by XI if XI is a variable. All
these derivations from variables are in
fewer than K steps. If XI is a variable
and the piece WI is not empty, then the
inductive hypothesis tells us that XI
derives WI in the new grammar. When we
construct the new grammar we replace the A
production A goes to XI through Xn. By a
family of productions and one of these
eliminates from the body exactly those
XI's such that WI is epsilon. We know that
is the case because if WI is epsilon then
surely XI is nullable. We also know that
not all WI's are epsilon because W is not
epsilon. That is at least one XI is either
a terminal or it is a variable that we do
not need to remove from the body. Thus in
the new grammar, the first step can
replace A by a body consisting of all
those XI's such that WI is not epsilon. We
can continue the derivation in the new
grammar by a derivation from each XI that
remains of the non-empty string WI. We
know this derivation in the new grammar
exists by the inductive hypothesis. We
also need to show part two, if W is
derived from A in the new grammar then it
is non-empty and also derived in the old.
We're going to skip this part. So we're
now ready for new simplification of
grammars the eliminations of unit
productions. A unit production is one
whose body is a single variable. We can
eliminate all such productions. The, the
idea is to discover using a discovery
algorithm, all pairs of variables AB. Such
that A derives B by a sequence of unit
productions. Eventually, a sequence of
unit productions must end with the use of
some other kind of production. So we can
collapse the steps that use unit
productions into the next one that does
not use a unit production. That is if B
goes to alpha is a non-unit production and
A derives alpha by unit productions, then
we'll add A goes to alpha. Finally, we
drop all unit productions. At this point
we do not need the unit productions and
can drop them from the grammar. Here's the
algorithm that discover the pairs of
variables AB such that A derives B by unit
productions. For the basis, surely A
derives A by unit productions only. This
is a sequence of zero steps. For the
induction, suppose we already discover
that A derives B by unit productions, then
if B goes to C is a unit production, we
may add the pair AC. There are two proofs
that we need but we're not going to do
them here. First, an induction on the
number of rounds in the discovery process,
let's just show that the pairs we find are
valid. That is, they really are pairs AB
such that A derives B by unit productions.
Then conversely we can show by an
induction on the number of steps of a
derivation from A to B, using unit
productions, that we will in fact discover
the pair AB. Another proof that we're
going to skip is the proof that in new
grammar has the same language as the old.
Again, we have to prove something more
general, that A derives W in the new
grammar if and only if it does so in the
old grammar. Each production of the new
grammar simulates one or more steps of the
derivation of the old grammar. That is,
some number of unit productions, perhaps
zero, followed by a non-unit production.
Conversely, every use of a production in
the new grammar can be replaced by zero or
more unit productions followed by a
non-unit production in the old grammar. We
can now combine the three simplifications
to make a strong statement about grammars.
If L is a context-free language, then L
minus epsilon has a grammar with no
useless symbols, no epsilon productions
and no unit productions. Another way to
put it is that L minus epsilon has a
grammar in which every production body is
either a single terminal or has length at
least two. You plot the constructions just
learned, but we have to be careful about
the order. You must start by eliminating
epsilon productions. We have to do this
step first because eliminating epsilon
productions can produce unit productions
that weren't there before and as we saw in
an example, it can create useless symbols
that were not useless before. That can
only occur if the production was only used
to derive the empty string, however.
Second, eliminate the unit productions.
Third, eliminate variables that derive no
terminal strings. We explained earlier why
this step must precede the next step in
our quest to eliminate all useless
symbols. So finally we do the fourth step
of eliminating all the unreachable
symbols. We've almost got our grammars
into Chomsky Normal Form or CNF. Such a
grammar has only two kinds of production
bodies: single terminals or two variables.
We're now going to give the construction
of the CNF grammar for L minus epsilon,
where L is any context-free grammar.
Incidentally, one important use of putting
grammars in CNF is it gives us a
relatively efficient algorithm for testing
membership in a string of a context-free
language. One might imagine that it was
easy to make such a test while looking at
all derivations of a certain limited
length. But with epsilon productions and
unit productions in the grammar, it is not
obvious how long the derivation of even a
short string of terminals has to be.
Moreover even if we can bound the light
for the derivation as we can Would still
be faced with an algorithm that took an
amount of time that is exponential in the
length of the terminal string. Rather by
putting the grammar in CNF we can make
this test and at most, we can make the
length of the string. Our first step is to
the cleaning we just described. The result
is the grammar no longer the empty string
even if the old one did. But otherwise the
languages are the same. But all production
bodies are either single terminal or have
length at least two. Our second step is to
turn those bodies that aren't a single
terminal into bodies into all variables.
The trick is simple, for each terminal
little A, create a new variable that we'll
call A sub A. To that. The job of this
variable is just to generate the terminal
little A. So replace A in all bodies of
length two or more by A sub A and add the
production A sub A goes to A. That is, of
course, that. Here's an example involving
the production A goes to B little CB
little E C and D are terminals so we must
have created variables A sub C and A sub E
with their productions A sub C and A sub E
goes to E. Then we can replace A goes to
BCDE by A goes to B A sub C D A sub E. Now
all production bodies that aren't a single
terminal are strings of two or more
variables. If exactly two that's great
because that's what CNF requires. But if a
body consists of three or more terminals,
we have to break the body into pieces into
variables that appear nowhere else. An
example should make the idea clear. If we
have a production AB goes to BCDE, Then we
need two new variables say F and G and
they are used only for this production.
They may not appear in the new grammar
except as we describe here. In general if
the body consists of N variables, we need
N minus two new variables. The job of the
first new variable F is to generate the
whole body except for the first symbol, B
in this case. That is we'd replace this A
production by A goes to BF. Now F needs to
derive CDE that's the rest of the body.
But that's too long so we use G to help. G
derives only BE, that's this production,
using the production G goes to DE and the
production for F becomes F goes to CG Plus
we've replaced A goes to BCDE by the three
productions that meet the CNF requirement.
A goes to BF, F goes to CG and G goes to
DE. These are the three productions can
simulate the effect of the original
production although they take three steps
to do so. Thus, making this change surely
allows the new grammar to generate
anything the old one did. But the new
grammar doesn't generate anything the old
one didn't, so the languages are the same.
The reason is that once we choose to
replace A by BF we are forced to replace F
by CG and then G by DE because these two
variables have only one production. Thus
using A goes to BF in the new grammar is
[inaudible] to using A goes to BCDE in the
old We thus have an argument why the
transformation from clean grammars from
clean grammars to CNF grammars did not
change the language. You can do formal
inductions on the length of derivations in
these grammars but I hope these less
formal arguments are convincing.