4
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 1. The link which Raphael provides does not solve this problem. 2. This question has been up for 8 months. Just now someone intends to mark it as a duplicate (when, again, it isn't)? This couldn't be more inappropriate. $\endgroup$ – لويس العرب Jan 2 '15 at 17:14
  • $\begingroup$ If the question really is a duplicate, it doesn't matter how much time elapses between the question being asked and somebody noticing that it's been asked before. The linked question explains how to prove that a grammar generates a particular language, and your question is exactly that. You're asking what techniques to use and the other question does that. I'm satisfied that it's a duplicate, even though the other question doesn't mention the specific language you're asking about. $\endgroup$ – David Richerby Jan 2 '15 at 17:58
  • $\begingroup$ The explanation provided by examples on that page is not at all clear, the techniques are not well-explained, the author uses notation which is completely foreign and not explained at all, and on top of this the entry seems to be taken from a larger tractate which might be more informative with regard to these matters. So, no, it's inconceivable to me how his entry could be of much help to my question, let alone provide the basis on which someone could conclude the current question is a duplicate. $\endgroup$ – لويس العرب Jan 2 '15 at 18:40
  • $\begingroup$ I might add that the users opinion -- many of us are self-taught, or view stackexchange as a useful addition to formal education -- should matter here, and there probably should be a stricter definition for what counts as a duplicate. Does it solve the exact same problem? If not, for the sake of pedagogy, let it alone. $\endgroup$ – لويس العرب Jan 2 '15 at 18:55
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – لويس العرب Apr 28 '14 at 3:07
  • $\begingroup$ @لويسالعرب 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. $\endgroup$ – Yuval Filmus Apr 28 '14 at 3:11
  • $\begingroup$ 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? $\endgroup$ – لويس العرب Apr 28 '14 at 5:02
  • $\begingroup$ @لويسالعرب 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. $\endgroup$ – Yuval Filmus Apr 28 '14 at 6:20
2
$\begingroup$

Ok, so here's my attempt at a solution, after not having looked at the problem since April. I think this is on the right track.

Given Yuval's helpful comment, we are to show (1) that every word $w$ generated by $G$ is in $L$ (2) every word $W$ in $L$ is in $G$

To show (1), we proceed by induction on the length $m$ of a derivation using the rules of $G$. There are two cases: either (i) $m$ = 1 (ii) $m$ $>$ 1.

Basis: $m$ = 1. Thus we have applied the first rule once, and must be $S$ $\rightarrow$ $\lambda$ and so we have $\lambda$ = $a$$^0$$b$$^0$, which is in $L$.

Induction step: $m$ $>$ 1. Suppose for inductive hypothesis the claim holds for all $n$ $<$ $m$ to show $m$, i.e. every stage $n$ $<$ $m$ in the derivation using rules of $G$ is in $L$ to show that the entire derivation of length $m$ is in $L$. Then the rule applied must be of the form $S$ $\rightarrow$ $a$$S$$b$, and we have a derivation of $a$$^m$$S$$b$$^m$. By inductive hypothesis, we can apply the rule $S$ $\rightarrow$ $\lambda$ once and have $a$$^m$$b$$^m$ which is in $L$.

To show (2): Induction on $i$, which is the number of repetitions symbols $a$, $b$ which is held constant.

Basis: $i$ = 0. Then $a$$^0$$b$$^0$ = $\lambda$, and clearly $\lambda$ $\in$ $G$ by the production rule $S$ $\rightarrow$ $\lambda$.

Induction step: $i$ $+$ 1 $>$ $i$. Suppose for induction hypothesis that the claim holds for all $i$ $<$ $i$ + 1 i.e. for all $i$ < $i$ + 1, words $w$ having $i$ $+$ 1-many repetitions $a$ and $i$ $+$-many repetitions of $b$ (consecutively) are in $G$. We wish to show that a word $w$ with $i$ $+$ 1-many consecutive repetitions of $a$, $b$ is in $G$. To this end, we simply apply the second rule $S$ $\rightarrow$ $a$$S$$b$ Until we get to the desired length.

| cite | improve this answer | |
$\endgroup$

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