Return to Answer

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.

Proof: (by induction on the length of the string)

Base case: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

Induction:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^* \alpha = (...)$ and $S\Rightarrow^* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^* ((...))$.

Then I would show that any string generated by the grammar consists of balanced strings.

Proof: by induction on the length of a derivation.

Base case: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

Induction: Fix $n$ - length of a derivation leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into terminal a string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L_2$.

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.

Proof: (by induction on the length of the string)

Base case: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

Induction:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^* \alpha = (...)$ and $S\Rightarrow^* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^* ((...))$.

Then I would show that any string generated by the grammar consists of balanced strings.

Proof: by induction on the length of a derivation.

Base case: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

Induction: Fix $n$ - length of a derivation leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into a terminal string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L_2$.

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.

Proof: (by induction on the length of the string)

Base case: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

Induction:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^* \alpha = (...)$ and $S\Rightarrow^* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^* ((...))$.

Then I would show that any string generated by the grammar consists of balanced strings.

Proof: by induction on the number derivations.

Base case: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

Induction: Fix $n$ - number of derivations leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into terminal a string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L_2$.

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.

Proof: (by induction on the length of the string)

Base case: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

Induction:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^* \alpha = (...)$ and $S\Rightarrow^* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^* ((...))$.

Then I would show that any string generated by the grammar consists of balanced strings.

Proof: by induction on the length of a derivation.

Base case: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

Induction: Fix $n$ - length of a derivation leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into terminal a string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L_2$.

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string consists of balanced strings then it is generated by the grammar. Then I would show that any string generated by the grammar consists of balanced strings. This can be easily proved using the length of strings and/or the induction on number of derivations.

Analogously for the language $L_2$.

In fact you are given two languages

1. $L_1$ defined as a set of strings of balanced parentheses.
2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

I would go about this as following:

First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.

Proof: (by induction on the length of the string)

Base case: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

Induction:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^* \alpha = (...)$ and $S\Rightarrow^* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^* ((...))$.

Then I would show that any string generated by the grammar consists of balanced strings.

Proof: by induction on the number derivations.

Base case: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

Induction: Fix $n$ - number of derivations leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into terminal a string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L_2$.