Date: Wed, 08 Jan 1997 20:51:55 GMT Server: NCSA/1.4.2 Content-type: text/html
Consider the grammar G with start symbol S and productions
Suppose instead that we had asked you to prove that has an equal number of a's as b's
. Applying the definition of
, this means we would like to prove the following two facts:
Given: any where x has an equal number of a's and b's.
Prove: that there exists some derivation .
In your proof, you've been handed a string x and all that you know about it is that it has an equal number of a's and b's. That's why in this case, we choose to do an induction on the length of x. You can't do an induction on derivation length here because it is not known whether x can be derived from S (That's what you're attempting to prove).
The exam instructions noted one fact that we have about x: since x has an equal number of a's and b's, it must be of even length, that is, |x| = 2n where n is the number of a's (also, the number of b's). So what we're really doing here is an induction on n.
The base case is when n=0 and so . Since there is a production
, certainly
can be derived in one step, and
so the base case holds.
For the inductive hypothesis, we only have two choices here: should we use normal induction or strong induction? We don't really know which to use until we do the rest of the proof, so I'll list them both:
So in the case where x has a non-trivial prefix with an equal number of
a's and b's we have shown that . We need to handle
every x, though, so what about the case where x doesn't have any such
prefix? There are two sub-cases to consider:
Notice how in the above arguments, we argued that x was derivable in the
grammar based entirely on what we were given: the fact that
and x had an equal number of a's and b's. From this we reasoned about
what x might look like: it had some even length 2n, and it may or may
not have had a prefix with an equal number of a's and b's. To handle all
the possibilities of n, we did a proof by induction on n. We handled
whether
or not x had a prefix with an equal number of a's and b's as subcases
within the induction. This covered all the bases, so we proved it for all x.
What about if we wanted to prove statement 2)? In this case the proof would be structured as follows:
Given: any where
.
Prove: that x has an equal number of a's and b's.
Here, what you're given and what you're asked to prove are flipped. You're
told that x can be derived from S in some number of steps, that is,
that for some
. Since you're given
that x is derivable in i steps, it is perfectly legal to do an
induction on i, the length of the derivation, to prove
that x has an equal number of a's and b's.
I'll leave this proof as an exercise. What are the three derivation cases
you will use for this proof? Do you need strong induction here? What's
the base case?