Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
To apply induction, you need numbers somewhere. Where are they going to come from? We need a parameter that is a number. Typically, we use the length of something. (For example, length of words.) Do you see how to proceed? –  Andres Caicedo May 10 '13 at 23:06
add comment

2 Answers 2

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.