# A Question from Introduction to Formal Languages by Gyorgy E. Revesz; Exercise 1.1

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?

-

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$.

-
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