5
$\begingroup$

Let L be language of balanced parentheses.

(a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L.

(b) Prove If w is in L, then there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s.

After much thought, I don't seek what I'm supposed to be doing. All I know is that I'm supposed to be using induction.

Here is the grammar that generates L: $S\to SS|(S)|\epsilon$

$\endgroup$
3
$\begingroup$

You are given two different definitions of the language of balanced parentheses:

  1. $w \in L$ iff $w$ contains an equal number of "(" and ")", and every prefix of $w$ contains at least as many "("s as ")"s.
  2. $L$ is generated by the grammar $S \to SS | (S) | \epsilon$.

You need to show that both definitions are the same. The easy direction is showing that each word generated by the grammar satisfies property (1). You do this by induction - either induction on the length or "structural" induction, which in this case is induction on the number of derivation step (base case: $S \to \epsilon$, steps: $S \to SS$, $S \to (S)$). The other direction is more complicated. You need to use complete induction; given a word $w$ satisfying (1), figure out which production needs to be applied first, and which parts of the word it generates, and then appeal to the induction hypothesis.

$\endgroup$
  • $\begingroup$ I have no idea what you are talking about. I don't need to prove two definitions. I need to prove your (1). $\endgroup$ – user678392 Sep 23 '13 at 16:45
  • 1
    $\begingroup$ @user678392 The question is to know what is your precise definition of the language of balanced parentheses. It is not so easy to give a formal definition. $\endgroup$ – J.-E. Pin Sep 23 '13 at 17:23
  • $\begingroup$ It was never given. I just assumed it meant that the number parentheses was equal and there was a matching left parentheses for every right one. $\endgroup$ – user678392 Sep 23 '13 at 17:28
  • $\begingroup$ I know the grammar that generates L. S->SS|(S)|epsilon $\endgroup$ – user678392 Sep 23 '13 at 17:52
  • 2
    $\begingroup$ @user678392 I'm afraid you are wrong and I am right. The question doesn't ask you to prove that (a) and (b) are equivalent, it asks you to prove (a) and (b), which is the same as proving (1) and (2) are equivalent. I encourage you to understand why, but you'll have to do it yourself. $\endgroup$ – Yuval Filmus Sep 23 '13 at 21:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Hint. Since you don't have a formal definition for $L$, I suggest to use the following one: $L$ is the context-free language generated by the grammar $$ S \to SS + (S) + 1 $$ where $1$ is the empty word. Now you can try to prove (1) and (2). In my opinion, (2) might be easier.

$\endgroup$
  • $\begingroup$ So I was given this grammar. Now, I don't know how to prove (1) and (2). $\endgroup$ – user678392 Sep 23 '13 at 19:22
  • $\begingroup$ w is in L. S generates w. then ... $\endgroup$ – user678392 Sep 24 '13 at 14:00

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.