Why is ))(() not in P?

Question

Suppose P is a set of balanced parentheses. Balanced parentheses is defined inductively and recursively as such:

1. $\lambda$ is an empty balanced parentheses
2. $\lambda\in P$
3. if $w\in P$, then $(w)\in P$.
4. if $w_1\in P$, $w_2\in P$, then $w_1w_2\in P$.

As a human, by common sense, since ))(() has a ) at front, it violates the definition of balanced parentheses.

But my question is, how to use the definition above rigorously to prove this proposition since I am so troubled by can't using both direct and contrapositive proof?

Answer 1

It's clear from the construction that a balanced parentheses will start with a $($ or be empty. This is because they are all constructed from $\lambda$ using the rules 1, 2, 3 and 4 and none of the rules can make a parentheses start with $)$ starting from parentheses that don't start with a $)$.

This is proved inductively. Let $P_n$ be the set of all balanced parentheses after $n$ or fewer applications of the 4 rules starting from $\lambda$. So $P_0=\{\lambda\}$, $P_1=\{\lambda, ()\}$ etc. Assume that no element of $P_n$ starts with a $)$, then clearly no element of $P_{n+1}$ does. Furthermore $P_0$ contains no element starting with $)$. To finish this off, we note that every balanced parentheses must belong to $P_n$ for some $n$.

Answer 2

It is easy to show by induction that

• Number of ('s equals the number of )'s.

Your sequence violates that.

It's also easy to show by induction (and follows immediately from the above), that all generated sequences have an even length. The length of your sequence ))(() is odd.