0
$\begingroup$

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align}

Please provide a formal proof for the following claim: $$ L(G) = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}. $$

Improve this question
$\endgroup$
  • $\begingroup$ They aren't equal $L(G) = \{ a^i (ab)^j c^j|i,j\geq0\}$, which is different from $L$. You probably misread something about the definition of $G$ or $L$. $\endgroup$ – plshelp Nov 1 '20 at 9:25
  • $\begingroup$ Hi, thanks for pointing out my mistake in the original post. $\endgroup$ – ZBear Nov 1 '20 at 9:29
  • 1
    $\begingroup$ This question is modified from an assignment; I changed the grammar and L to learn the idea of proving this type of question. $\endgroup$ – ZBear Nov 1 '20 at 9:32
  • $\begingroup$ I know how to do S->uSw|$\epsilon$, S->XY, and S->X|Y. However, I don't know how to approach S->S|X $\endgroup$ – ZBear Nov 1 '20 at 9:37
  • $\begingroup$ Is $S\rightarrow S|X$ different from $S\rightarrow Y, Y\rightarrow Y|X$? How? $\endgroup$ – greybeard Nov 1 '20 at 10:13
0
$\begingroup$

Let $L = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}$. The proof consists of two steps:

  • $L \subseteq L(G)$.
  • $L(G) \subseteq L$.

The first step proceeds by direct construction: we show how to produce each word in $L$ using the grammar. In order to produce the word $a^i (ab)^j c^j$, we first apply $i$ times the rule $S \to aS$, then once the rule $S \to B$, then $j$ times the rule $B \to abBc$, then once the rule $B \to \epsilon$. Formally, we could prove that this works by induction.

For the second step, we first prove by induction that all words generated by $B$ are of the form $(ab)^jc^j$. We show that by induction on the length of a production starting at $B$. If the first step is $B \Rightarrow \epsilon$ then we generate $\epsilon$. Otherwise, the first step is $B \Rightarrow abBc$. By induction, the $B$ on the right produces a word of the form $(ab)^jc^j$, and overall the produced word is $(ab)^{j+1}c^{j+1}$, which is of the same form.

We can now prove the required claim by induction on the length of a production starting at $S$. If the first step is $S \Rightarrow B$, then the preceding paragraph shows that the generated word is of the form $(ab)^jc^j$. Otherwise, the first step is $S \Rightarrow aS$. By induction, the $S$ on the right generates a word of the form $a^i (ab)^j c^j$, and overall the produced word is $a^{i+1} (ab)^j c^j$, which is of the required form.

Improve this answer
$\endgroup$
  • $\begingroup$ Hi, thanks for your answer. Could you give the inductive hypothesis for the induction in the first step? Many thanks. $\endgroup$ – ZBear Nov 1 '20 at 10:03
  • $\begingroup$ If $B \Rightarrow^n w$ then $w \in \{ (ab)^j c^j : j \in \mathbb{N} \}$. $\endgroup$ – Yuval Filmus Nov 1 '20 at 10:07
  • $\begingroup$ I think your I.H is for the second step. $\endgroup$ – ZBear Nov 1 '20 at 11:12
  • $\begingroup$ Right, this is the IH for the second step. You'll have to work out the first step on your own. I'm not going to write a full-fledged answer with all details. $\endgroup$ – Yuval Filmus Nov 1 '20 at 11:21
  • $\begingroup$ I finished a complete proof under you guide, many thanks. $\endgroup$ – ZBear Nov 1 '20 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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