Recapping the rules of grammar G, for reference:
\(S \ \rightarrow \ a \ \mid\ aB \)
\(B \ \rightarrow \ aaS \ \mid\ BB \)
Now, let's strengthen our claim. First, create a modified grammar G' which is just like G except that both S and B are allowed as start symbols. Any tree generated by G is also generated by G'. Second, we'll prove a modified claim that includes information about trees with label B on the root.
New claim: If T is generated by G', then L(T) is congruent to 1 (mod 3) if the root of T has label S and L(T) is congruent to 0 (mod 3) if the root of T has label B.Proof by induction on h, which is the height of the tree.
Base: h=1. The only tree of height 1 consists of a root S with a single child node labelled a. The terminal string has length 1, which is congruent to 1 (mod 3).
Inductive hypothesis: Suppose that any tree T of height 1 through k-1 (\(k \ge 2\)) generated by G' has L(1) congruent to 0 (mod 3) if the root of T has label B, otherwise congruent to 1 (mod 3).
Rest of inductive step:
Let T be a tree of height k generated by G'. Since (\(k \ge 2\)), there are three cases for what the top nodes in T might look like:
(1) S (2) B (3) B / \ / | \ / \ a B a a S B B (subtree P) (subtree P) (subtree P) (subtree Q)In all three cases, subtrees P and Q have height less than k, so the inductive hypothesis applies to them.
Case 1: By the inductive hypothesis, since the root of P has label B, L(P) is congruent to 0 (mod 3). T contains one additional leaf node with label a, so L(T) is congruent to 1 (mod 3). This is what we needed to show since the root of T has label S.
Case 2: By the inductive hypothesis, since the root of P has label S, L(P) is congruent to 1 (mod 3). T contains two additional leaf nodes with label a, so L(PT) must be congruent to 0 (mod 3). This is what we needed to show since the root of T has label B.
Case 3: By the inductive hypothesis, since the roots of P and Q have label B, L(P) and L(Q) are both congruent to 0 (mod 3). L(T) = L(P) + L(Q). So L(T) must also be congruent to 0 (mod 3). This is what we needed to show since the root of T has label B.
The base case should be h=1. This grammar doesn't generate trees of height 0.
Did you clearly describe the (only possible) tree with h=1 and check the claim for this tree?
In the inductive hypothesis, did you clearly state the range of heights for which the claim is supposed to hold? Is the top value in this range (k-1 in the above) one less than the height of the tree you chose in the inductive step (k in the above)?
Did you force k (the height of the big tree in the inductive step) to be larger than the base case? That's very useful in this kind of proof, because it means you don't have to re-do the base case possibilities in the inductive step. That's why we have only three cases (not four) in the above proof.
Does your inductive step cover all three cases?
Did you show pictures of what the tree looks like in each case? This is technically not required for a complete proof, but it's very helpful to the reader. It also provides a safety net for you if your words and algebraic notation are buggy or imprecise.
In case 3, did you use different names for the two subtrees? The two subtrees don't need to look identical.
In case 3, did you assume that subtree P and/or Q has height k-1? Don't do that. One of the two subtrees may be shorter than k-1.
Finally, does your proof have lots of words? Correct spelling and punctuation? Sensible division into paragraphs? Is this clear enough that you could send it to your friend at Princeton who's also taking Discrete Math? No? Then write it out properly. How will you be able to write literate math under exam conditions if you don't practice writing when you study?