Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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? – Andrés E. Caicedo May 10 '13 at 23:06

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

share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.