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

Given two CFGs for balanced parentheses.

1. $$S \rightarrow SS \mid (S) \mid \epsilon$$

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

• You can show that both grammars generate the language of balanced parentheses. – Yuval Filmus Feb 7 at 16:28

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.

• "all words not longer than" should probably be "all words in $B$ not longer than" – Alexey Romanov Feb 8 at 6:59
• @AlexeyRomanov Thanks, updated. – Apass.Jack Feb 8 at 7:03

Let $$T = \{ (, ) \}$$ be the alphabet of terminals and $$N = \{ S \}$$ that of nonterminals. Additionally, let $$\Rightarrow_i$$ denote a derivation using the grammar for $$L_i$$, $$i \in \{ 1, 2 \}$$.

Let $$w \in L_1 \setminus \{ \varepsilon \}$$. Then $$S \Rightarrow_1^\ast w$$ and $$w$$ contains at least one pair of parentheses; in order to produce it, the rule $$S \to (S)$$ must be used somewhere (since it is the only rule which contains parentheses at all). Thus, there is $$w_1, w_2 \in (N \cup T)^\ast$$ and $$w_3 \in L_1$$ with $$S \Rightarrow_1^\ast w_1 S w_2 \Rightarrow_1 w_1 (S) w_2 \Rightarrow_1^\ast w_1 ( w_3 ) w_2 \Rightarrow_1^\ast w$$ and such that this is the first use of the rule $$S \to (S)$$. Now, since this is first derivation in which the rule $$S \to (S)$$ is used, $$w_1, w_2 \in \{ S \}^\ast$$ and both were produced by using (only) the other two rules of the $$L_1$$ grammar. As a result, $$S \Rightarrow_1^\ast w_1$$ and $$S \Rightarrow_1^\ast w_2$$.

Using induction on the number of pairs of parentheses in $$w$$ (since $$w_1$$, $$w_2$$ and $$w_3$$ all have at least one pair less than $$w$$) yields $$S(S)S \Rightarrow_2^\ast w_1 (w_3) w_2 \Rightarrow_2^\ast w$$, as desired.