I have the following Context free grammar where:
S → SS
S → hSm
S → ε
and the question I'm answering is:
"Prove by induction on n,that for all n ≥ 0, the string $h^n$$m^n$ has a derivation in this grammar of n + 1 steps."
Here's what I've tried proving:
Base step: When n = 0, we have $h^0$$m^0$ whereby it holds true since
it can be represented by the context free grammar.
Inductive step: Assume k is true for some integer k ≥ 0 hence we can
say that $h^k$$m^k$ holds. We now want to prove for k+1 with that
h^k+1 m^k+1. If we take k = 2, then can derive the string hhhmmm
which can also be represented by the context free grammar hence, we
have proven that the derivation of this grammar of n+1 steps is true.
I have doubts about my prove and I'm not certain if I'm proving it correctly. Would appreciate some feedback on what can be improved.
For the base case, you should (at this point) be more explicit even for relatively trivial statements. Why is $h^0m^0$ representable by the grammar?
Your inductive case is just completely wrong structurally. You've assumed that $k$ is some arbitrary natural number, you can't then "take it to be $2$". The best you could do is say "if $k=2$ then ..." but then you'd still need to cover the $k\neq 2$ case. As it is, the antecedent and consequent of that sentence are almost entirely unrelated. How does "proving" the $k=2$ case imply anything about the $k=7$ case, say, let alone the arbitrary $k$ case? And here too, you should be more explicit how the strings are "representable by the grammar".
For the inductive case, you know, via the inductive hypothesis, that you have a derivation of $h^km^k$. You need to show how to build a derivation for $h^{k+1}m^{k+1}$ from it. Your inductive case should talk about how you are modifying/extending the derivation of $h^km^k$, and how those modifications/extensions are justified.