Proof by induction on Context Free Grammars

Question

So I have this problem I am working on regarding inductive proofs on Context Free Grammars.

Given this grammar

S-> aSb | SS | ab

Prove using induction that no string generated by the grammar starts with abb.

It's easy to see that this is in fact true, but I have some problem with how make a formal proof of it.

I'm thinking either using course by value induction on the length of the word, or course by value induction on the length of the derivation(don't really know which one is better in this case).

Let's use induction on the length of the derivation.

Base case: The length of the derivation is one step, then the only possibilility is S-> ab, which clearly holds.

Inductive hypothesis: if S=>w' with n derivations(n>0), then w' does not start with abb

Inductive step:??

The inductive step is where I'm having my problems, and I don't really understand what to do.

I'm wondering if some one can explain what I'm supposed to do there?

Thanks!

Answer 1

For any induction on n, the base case is P(0) or P(1), the induction hypothesis is P(n), and the induction step is to prove that P(n) implies P(n+1). So you want your induction step to be:

Induction step: Given that for all w' such that S => w' with n derivation steps, w' does not begin with the string abb, prove that for all w'' such that S => w'' with n+1 derivation steps, w'' does not begin with the string abb.

Put another way: If for all derivations of length n, we have the property that w does not begin with abb, we wish to prove that for all derivations of length n+1 the same property holds.

Every derivation of length n+1 has one of S -> aSb, s -> SS, or s -> ab. (If we require that n > 0, the the last does not apply.) So you want a case analysis.

Case 1: S -> aSb. If S can expand to a single b, or to a string beginning bb, we've disproved the conclusion. We can establish the conclusion for this case if we can prove that no word in the language begins with b, or equivalently that every word begins with a.

Case 2: S -> SS. The initial string abb must either be

• all in the first S of the RHS, or
• partly in the first S, or
• (if the first S rewrites to the empty string) at the beginning of the second S.

The first and last of these are ruled out by the induction hypothesis. So how many ways can we define the prefix 'abb' between the first S and the second? I count two: 'a' + 'bb', and 'ab' + 'b'. If we can prove that these are both impossible in any word of the language, we are home free.

So, if it were my task to produce this proof, I'd start by proving that no word in the language begins with 'b', and use that to dispose of the two cases.