How to prove the equivalence of two CFG for balanced parentheses?

Given two CFGs for balanced parentheses.

-
$S \rightarrow SS \mid (S) \mid \epsilon$

-
$S \rightarrow S(S)S \mid \epsilon$

How do I show that they are equivalent?

I have been able to show $ L(2) \subset L(1) $ as follows

$$ S \Rightarrow SS \Rightarrow SSSS \leadsto S(S)S $$

Thus, $ S \leadsto S(S)S $. Keeping production rule $ S \rightarrow \epsilon $, we get $ L(2) \subset L(1) $.

But I can't prove the reverse i.e. $ L(1) \subset L(2) $. Any help would be appreciated.

But I can't prove the reverse i.e. $(1)\subseteq (2)$.

Indeed, that direction of inclusion is somewhat harder to prove.

Let us prove all following 3 context-free grammars are equivalent

• $G_1$: $S \rightarrow SS \mid (S) \mid \epsilon$

• $G_2$: $S \rightarrow S(S)S \mid \epsilon$

• $G_3$: $S \rightarrow (S)S \mid \epsilon$

Proof.

• $L(G_1)\supseteq L(G_2)$:

$S\Rightarrow_{G_1}SS\Rightarrow_{G_1}SSS\Rightarrow_{G_1}S(S)S\,.$

• $L(G_2)\supseteq L(G_3)$:

$S\Rightarrow_{G_2}S(S)S\Rightarrow_{G_2}(S)S\,.$

-
$L(G_3)\supseteq L(G_1)$:


Let $B$ be the language of balanced parentheses, i.e.,
$$\{x\in\{(,)\}^*\}:|x||_(= ||x||_) \text { and, }\text{if } f\text{ is a prefix of } x,\,|f||_(\ge ||f||_)\}\,.$$ It is immediate to see that $L(G_1)\subseteq B$ by structural induction.

Let $P(n)$ be the proposition that all words in $B$ not longer than $2n$ are in $L(G_3)$.

• $P(0)$ is true since the only word not longer than 0 is $\epsilon$.

• Assume $P(k)$ is true. Let $w\in B$ with length $2(k+1)$. $w$ must start with left parenthesis, "(". If we count the number of "("s and the number of ")" in $w$ starting from the beginning "(", there will be a time the number of ")"s catches up with the number of "("s. Consider the first time that happens, which must at a ")" in $w$. So $$w=(w_1)w_2$$ for some $w_1,w_2\in B$. By IH, $S\leadsto_{G_3}w_1$ and $S\leadsto_{G_3}w_2$. Hence

$$S\Rightarrow_{G_3}(S)S\leadsto_{G_3}(w_1)w_2=w$$
which shows $P(k+1)$ is true, completing mathematical induction.

All $P(n)$ tell that $L(G_3)\supseteq B$.

Exercise. Let $G_4$ be the grammar $S \rightarrow S(S)\mid \epsilon$. Show that $G_4$ also generates the language of balanced parentheses.

StackExchange Computer Science Q#103977, answer score: 4