Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The exercise says

"Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$ generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$."

Now, I'm new to this subject although I'm familiar with the theory of Turing machines and automata. I'm teaching myself (not in a class, completely independently) from scratch. Please go easy on me.

Now, two questions:

(1) I suspect the way to do this proof is by induction on $i$, which is to say induction on the iterations of letters in the alphabet or the length of the word formed by iterations of $a, b$. Is this assumption correct?

(2) If the assumption in (1) is not correct, what is the correct strategy?

share|improve this question
add comment

1 Answer 1

Generally speaking, you need to do two things:

  1. Prove that every word generated by $G$ is in $L$.
  2. Prove that every word in $L$ can be generated by $G$.

Hints for (1): Prove by induction on the length of the derivation.

Hints for (2): Prove by induction on $i$.

share|improve this answer
Thanks, Yuval. If I may press a little more: I assume that the basis of the derivation will be S --> $\lambda$ and the induction case is supposed to be S --> $a$S$b$? –  لويس العرب Apr 28 at 3:07
@لويسالعرب That's what the proof will amount to. But the induction is on the length of the derivation. If the derivation is of length $1$ then the first rule must be $S \to \lambda$, otherwise it must be $S \to aSb$ and then you can apply the induction hypothesis. –  Yuval Filmus Apr 28 at 3:11
Ok, so just to make sure I'm following so far: For (1), by induction on the length of a derivation of w from G. Case 1. Derivation is of length 1. Then the first rule is applied, i.e. w = $\lambda$. <END CASE 1>. Case 2. Derivation is of length n, for n > m, and suppose that the claim holds for all m < n. So the derivation of w looks like S --> aSb containing n steps. By hypothesis, there will be derivations of w of length m < n ; so S --> w m-many times . . . something along these lines? –  لويس العرب Apr 28 at 5:02
@لويسالعرب I'm not going to make any more detailed comments. You will have to make do with my answer. If in doubt, try to find a more knowledgeable friend to help you. –  Yuval Filmus Apr 28 at 6:20
Thanks -- will re-read chapter and try again later. –  لويس العرب Apr 28 at 7:21
add comment

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.