How to use induction to prove this argument?

120 Views Asked by At

enter image description here

It is obvious that this grammar will always return an equal number of both a's and b's. But I was wondering how to prove it using induction? I understand induction, but I was finding it hard to apply to this situation.

The ε character denotes an empty.

2

There are 2 best solutions below

0
On

Hint: use induction on number of steps made to get string of a,b,S,T

0
On

Let $P(n)$ be the assertion that if $w\in\{S,T,a,b\}^*$ can be derived in $n$ steps, then $|w|_a=|w|_b$, where $|w|_x$ is the number of occurrences of the letter $x$ in $w$.

Initially, when you begin a derivation, you have the string $S$, and $|S|_a=0=|S|_b$, so $P(0)$ is true. Suppose that $P(n)$ holds for some $n\ge 0$, and let $w\in\{S,T,a,b\}^*$ be derivable in $n+1$ steps. Suppose that the last step is $v\Rightarrow w$. Then $v$ is derivable in $n$ steps, so $|v|_a=|v|_b$. Moreover, $v$ must be of the form $xSy$ with $x,y\in\{S,T,a,b\}^*$ or of the form $xTy$ with $x,y\in\{S,T,a,b\}^*$, since a further step is possible. Now see if you can use the induction hypothesis $P(n)$ to finish the induction step by showing that $|w|_a=|w|_b$; I’ve done so below, in the spoiler-protected block.

If $v=xSy$, then $w=xy$, or $w=xTSy$; in either case $|w|_a=|v|_a=|v|_b=|w|_a$. If $v=xTy$, then $w=xy$ or $w=xaTby$. The first possibility has already been covered, and in the second we have $|w|_a=|v|_a+1=|v|_b+1=|w|_b$. In all cases, then, $|w|_a=|w|_b$, so $P(n+1)$ holds. By induction $P(n)$ holds for all $n\ge 0$. In particular, all terminal $w$ strings produced by this grammar satisfy $|w|_a=|w|_b$, which is the desired result.