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.