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

$\endgroup$
6
  • $\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, 2020 at 9:25
  • $\begingroup$ Hi, thanks for pointing out my mistake in the original post. $\endgroup$
    – ZBear
    Nov 1, 2020 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, 2020 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, 2020 at 9:37
  • $\begingroup$ Is $S\rightarrow S|X$ different from $S\rightarrow Y, Y\rightarrow Y|X$? How? $\endgroup$
    – greybeard
    Nov 1, 2020 at 10:13

1 Answer 1

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.

$\endgroup$
5
  • $\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, 2020 at 10:03
  • $\begingroup$ If $B \Rightarrow^n w$ then $w \in \{ (ab)^j c^j : j \in \mathbb{N} \}$. $\endgroup$ Nov 1, 2020 at 10:07
  • $\begingroup$ I think your I.H is for the second step. $\endgroup$
    – ZBear
    Nov 1, 2020 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$ Nov 1, 2020 at 11:21
  • $\begingroup$ I finished a complete proof under you guide, many thanks. $\endgroup$
    – ZBear
    Nov 1, 2020 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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