Struggling to understand how to use Structural Induction to prove a recursively defined Set

Question

The recursively defined Set:

I. BASE: () is in P.

II. RECURSION:
a. If E is in P, so is (E).
b. If E and F are in P, so is EF.

III. RESTRICTION: No configurations of parentheses are in P other than those derived from I and II above.

I have to demonstrate whether or not (()()))(() is in P. I know that I can define a function, f(S), that equals [# of left parenthesis] - [#right parenthesis], where f(s) = 0. Using that test, (()()))(() fails. But even though my professor used f(s) to prove other sets of unbalanced parenthesis are not elements of S, he says this test is not totally adequate in explaining why (()()))(() is not an element of P. I'm not sure why. Can someone shed light on this?

EDIT: Just realized that (()()))(() actually succeeds the test - I miscounted. So it's clearly not adequate. Any ideas of how I can demonstrate that is not a legal string of parenthesis?

Answer 1

HINT: The problem with $s=(()()))(()$ is that $f(s)=0$ even though $s\notin P$. In order to use $f$ to see why $s\notin P$, you have to look at the value of $f$ on each initial substring of $s$.

$$\begin{array}{rcc} \text{substring }t:&(&((&(()&(()(&(()()&(()())&\color{crimson}{(()()))}&(()()))(&(()()))((&s\\ f(t):&1&2&1&2&1&0&\color{crimson}{-1}&0&1&0 \end{array}$$

Notice that when $t=(()()))$, $f(t)$ is negative.

It turns out that $s\in P$ if and only if $f(s)=0$ and $s$ has no initial segment $t$ such that $f(t)<0.$

One way to prove that $s\notin P$ is to prove the highlighted statement by structural induction. In less formal terms, the statement says that the strings in $P$ are precisely those that at no point have more right than left parentheses when you read them from left to right.