3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You can show that both grammars generate the language of balanced parentheses. $\endgroup$ – Yuval Filmus Feb 7 at 16:28
4
$\begingroup$

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.

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

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.

$\endgroup$

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.