Generated words, balance and unique parsing

Try

The strings (()())() and )( both contain equally many opening and closing parentheses. Only the first can represent properly nested brackets. Scan from left to right: a closing bracket cannot use an opening bracket that has not yet appeared. We will turn this observation into a proof, and then into a rule that parses every valid word in exactly one way.

A word is a finite sequence of symbols. Its length is the number of symbols, and ε denotes the empty word of length zero. Concatenation puts words next to each other. Let G be the smallest set containing ε and containing (u)v whenever it already contains u and v. “Smallest” excludes extra words: membership must have a finite construction from these rules. For instance, () is (ε)ε, while (())() is obtained using u=() and v=().

Predict

For each opening symbol add one to a running balance; for each closing symbol subtract one. Predict whether a total of zero alone certifies membership in G. Then predict where to split (()())() into (u)v. Several prefixes have total zero. Which return must correspond to the closing bracket paired with the very first opening?

Record the split before reading the trace. Notice that proving every constructed word passes a test is only one direction. To characterize G, we must also prove that every word passing the test can be constructed.

Experiment

Write B(j) for the balance after the first j symbols, including B(0)=0. Here is the complete trace for the worked word (()())().

Prefix length j	New symbol	Balance B(j)	Interpretation
0	none	0	Empty prefix
1	(	1	First opening
2	(	2	Nested opening
3	)	1	One nested pair closes
4	(	2	Another nested opening
5	)	1	That pair closes
6	)	0	First positive return to zero
7	(	1	Suffix begins
8	)	0	Word ends

Cover the last column and reconstruct it. Now try the later return j=8 instead: the proposed interior would be ()())(, which contains a negative-balance prefix. A zero at the end of a proposed outer pair is insufficient; its whole interior must be valid.

Understand

Let D contain exactly the words with nonnegative balance at every prefix and zero total balance. We prove G=D by two inclusions.

Constructed words pass the balance test. Use structural induction on a finite construction. The empty word passes. Suppose u and v pass. In (u)v, prefixes during the interior have balance 1 plus the corresponding balance of u, so they are at least one. The closing symbol brings the balance to zero. Prefixes extending into v then have exactly the corresponding balance of v. All are nonnegative, and the total is 1+0−1+0=0. Thus G is contained in D. We have not yet proved the reverse.

Every word passing the test is constructed. Use strong induction on length. The empty word is already in G. A nonempty word in D starts with an opening symbol, since a closing symbol would immediately give balance −1. Its final balance is zero, so there is a first positive index k at which it returns to zero. Before k the integer balances are at least one. Consequently the kth symbol is a closing symbol, taking balance one to zero.

Let u be the symbols between the first symbol and position k, and let v be the suffix after k. An interior prefix of length j has balance B(j+1)−1, which is nonnegative; the full interior has balance zero. A suffix prefix has balance B(k+j)−B(k), also nonnegative, with total zero. Both subwords are shorter than the original. Induction gives u,v in G, and the construction rule gives (u)v in G. This proves D is contained in G.

The decomposition is unique. In any representation (u)v with balanced u and v, the balance stays strictly positive until the closing symbol after u. That symbol must be the first return to zero. Its position determines both substrings. This is stronger than existence. Recursively applying the same argument terminates because subwords get shorter, producing one parse tree under this particular grammar.

Apply

Use the changed word (())()() to find the first return, the two subwords and their next splits. The first return is at position 4, with u=() and v=()(). Explain why the final zero cannot replace the first return. Then repair the false test “equal counts means valid” using )(: equal totals do not enforce nonnegative prefixes.

Unique parsing makes a recursive word function legitimate. Define N(ε)=0 and N((u)v)=1+N(u)+N(v). Smaller subwords guarantee termination; their unique choice guarantees an unambiguous value. Induction proves N(w) is half the word length, the number of pairs.

Now change the grammar to the three productions S→SS, S→(S), S→ε. It generates the same balanced words: concatenation and wrapping preserve the balance condition, and each old construction (u)v can be made by wrapping and concatenation. But it is ambiguous. The word () can be a wrapped ε or the concatenation of that wrapped ε with another ε. If a construction tree has height zero at ε and one plus the maximum child height at each production, these two trees have heights one and two.

Height is therefore a function of a derivation, not a well-defined function of the resulting word under those rules. Ambiguity does not invalidate every recursive quantity: pair count is still well-defined because every derivation yields half the resulting length. One must prove independence of the derivation, or choose and justify a canonical parse. Merely writing recursive equations does neither.

Continue

In the practice tasks, separate three claims: generated words satisfy a property; every word with the property is generated; and each generated word has a unique construction. Different proofs establish them. A structural-induction proof of an invariant usually establishes only the first.

Carry this distinction into syntax trees, recursive data types and algorithms. To define a function by structural recursion, check the permitted constructors, whether they overlap, the size decrease and whether different representations force the same output. A finite trace helps discover these conditions; the general first-return argument is what proves them for all balanced words.