# Formal proof of language accepted by a specific CFG

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

• 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$. – plshelp Nov 1 '20 at 9:25
• Hi, thanks for pointing out my mistake in the original post. – ZBear Nov 1 '20 at 9:29
• This question is modified from an assignment; I changed the grammar and L to learn the idea of proving this type of question. – ZBear Nov 1 '20 at 9:32
• 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 – ZBear Nov 1 '20 at 9:37
• Is $S\rightarrow S|X$ different from $S\rightarrow Y, Y\rightarrow Y|X$? How? – greybeard Nov 1 '20 at 10:13

## 1 Answer

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.

• Hi, thanks for your answer. Could you give the inductive hypothesis for the induction in the first step? Many thanks. – ZBear Nov 1 '20 at 10:03
• If $B \Rightarrow^n w$ then $w \in \{ (ab)^j c^j : j \in \mathbb{N} \}$. – Yuval Filmus Nov 1 '20 at 10:07
• I think your I.H is for the second step. – ZBear Nov 1 '20 at 11:12
• 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. – Yuval Filmus Nov 1 '20 at 11:21
• I finished a complete proof under you guide, many thanks. – ZBear Nov 1 '20 at 11:56