Language of balanced parentheses; Biconditional proof about parentheses

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$

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

• $w \in L$ iff $w$ contains an equal number of "(" and ")", and every prefix of $w$ contains at least as many "("s as ")"s.

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

StackExchange Computer Science Q#14557, answer score: 3