A finite automaton remembers one of finitely many states. That is enough for properties such as parity, but nested structure asks a different question: which closing parenthesis matches which opening one? A grammar can describe this structure recursively. To use the description rigorously, we must prove both that every generated word is valid and that every valid word can be generated.
There is another distinction to keep in view. A language is a set of words; a parse tree explains a word's structure. Two grammars may generate exactly the same words while assigning different numbers of trees to them. Balanced parentheses give a small example in which correctness, ambiguity, deterministic parsing and counting can all be proved explicitly.
A grammar rewrites one nonterminal at a time
Definition 8.1.1
(Context-free grammar, derivation and parse tree)
A context-free grammar is a tuple : is a finite set of nonterminals, is a disjoint finite terminal alphabet, is the start symbol, and is a finite set of productions , where and .
One derivation step replaces an occurrence of by a production's right-hand side, leaving the surrounding symbols unchanged. The language consists of terminal words obtainable from by finitely many steps. The empty word is ; it has length zero and is not an extra terminal symbol.
A parse tree is an ordered tree recording the productions used. An internal nonterminal's children spell its selected right-hand side. Reading terminal leaves from left to right gives the generated word, called its yield. An empty production contributes empty yield; it may be drawn with an leaf.
Because the left-hand side of a production is a single nonterminal, the same rule can be used wherever that nonterminal occurs. This is the context-free part of the definition. A derivation records the order of replacements; a parse tree records their nested structure.
Define balanced words independently of a grammar
Definition 8.1.2
(Balance and balanced words)
Our alphabet contains exactly ( and ). For a prefix , define its balance by
the number of opening symbols minus closing symbols. Let be the set of words such that every prefix has nonnegative balance and . The empty word belongs to .
Counterexample mode
Equal totals do not guarantee valid nesting
The word ())( has two opening and two closing symbols, so its final balance is zero. Its prefix ()) has balance , however: one closing symbol has no available opening partner. Thus it is not in .
For (()()), the successive nonempty prefix balances are , so the word is balanced. Both the prefix condition and final equality matter.
A simple grammar for this language is
The rules suggest concatenating two balanced words, enclosing one balanced word, or using the empty word. These operations preserve balance, but that observation proves only one direction of language equality.
Proposition 8.1.3
(Soundness of the first grammar)
Every word generated by is balanced: .
Proof
(Induction on the parse tree)
Induct on the finite parse tree. The empty production yields , which satisfies the conditions. If the tree uses and the child yields balanced , the word starts with balance 1, stays at least 1 while reading , and returns to zero at its final closing symbol.
If the root uses , its children yield balanced . Prefixes inside are nonnegative. After , the balance is zero, so prefixes continuing into have exactly the corresponding balances of . The concatenation ends at zero. Thus every production preserves the property and .
The first return to zero determines the decomposition
Proposition 8.1.4
(First-return decomposition)
Every nonempty has a unique factorization with . The displayed closing parenthesis is the first position at which the balance of a prefix of returns to zero, and and are shorter than .
Proof
(Splitting at the first return)
Take a nonempty word . It must start with (; otherwise the first prefix would have balance . Its total balance is zero, so there is a first positive position where the balance returns to zero. That position is a closing parenthesis, giving a factorization
The displayed outer pair ends at the first return. The inside word is balanced: its prefix balances equal the corresponding balances of minus one, and are nonnegative because has not returned to zero earlier. It ends at balance zero. The suffix is balanced because it begins after a zero-balance prefix and inherits the remaining prefix conditions.
Both and are shorter than . The first-return position also makes the factorization unique: in any factorization with , every prefix of has balance at least , so the displayed closing parenthesis is the first return.
Concept lensGeometric
Balanced words as height paths
Read ( as an up-step and ) as a down-step. Then is the height of the path after the prefix , and a word lies in exactly when the path never drops below height zero and ends at height zero. In this picture the first return is the first time the path comes back to the axis, so cuts the path into an arch, which is the path of raised by one step, followed by the path of . Counting such paths is the counting problem solved by the recurrence below.
Consider the grammar
Proposition 8.1.5
(Two grammars for the balanced words)
With as above, .
Proof
(Strong induction on word length)
Induct strongly on word length. The empty word uses . For nonempty balanced , take its first-return decomposition . By induction, the shorter balanced words have derivations from . Applying and substituting those derivations generates .
The same soundness reasoning as before proves that every word of is balanced, so . Moreover, can simulate each nonempty production of through . It therefore generates every balanced word as well. Combining this with soundness gives .
Worked example 8.1.6
(The first return splits nesting from the remaining suffix)
For (())(), the prefix balances are . The first return is at position four, so and . The outer pair surrounds only the first copy of (), while the second copy is the suffix.
A complete leftmost derivation in is
At each step we replace the leftmost remaining nonterminal. The empty productions are essential: they terminate both the innermost words and the final suffixes.
Different rewriting orders need not mean ambiguity
Definition 8.1.7
(Ambiguous grammar)
A grammar is ambiguous if some generated word has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations. Merely finding two arbitrary derivations is insufficient: one tree can be expanded in different orders.
Common mistake
(A different rewriting order is not a different tree)
For example, after in , we can expand the inside nonterminal before the suffix, or the suffix before the inside. These choices may give different intermediate strings, but they can still describe the same tree.
Worked example 8.1.8
(Two trees for () in the ambiguous grammar)
The grammar is genuinely ambiguous even for (). One tree uses at the root and the empty production inside. Another uses at the root, with a first child yielding () and a second child yielding . The root productions differ, so these are distinct trees with the same yield. In fact, further concatenations with empty words create still more trees; they do not create new terminal words.
Proposition 8.1.9
(The first-return grammar is unambiguous)
Every balanced word has exactly one parse tree in .
Proof
(Induction on word length)
Induct on word length. Only the empty production can yield the empty word, because the other production introduces a visible pair. Thus the empty word has one tree.
For a nonempty word, the root must use . If its children yield , soundness says both are balanced. Consequently, the closing symbol in the root production is precisely the first return of the whole word's balance to zero. The word therefore fixes that closing position and fixes both and uniquely.
Their lengths are smaller, so induction gives one tree for each child. This fixes the entire tree. Grammar is unambiguous, although generates the same language ambiguously.
Proof X-ray
Why the first return pins down the tree
The induction hypothesis is used only on the two children, which are strictly shorter. The step that is easy to miss is that the root production is forced: yields no symbol, so a nonempty word must start with . The non-obvious move is then to turn a statement about trees into a statement about the word: whichever tree is given, the closing parenthesis of its root production sits where the balance first returns to zero, and that position is determined by the word alone. So and cannot differ between two trees for the same word. The same argument fails for , because has no such anchor: the split of a concatenation can be at any position where the balance is zero, and empty productions can be inserted anywhere.
Common mistake
(Ambiguity of a grammar is not ambiguity of a language)
Ambiguity is therefore a property of a particular grammar. Showing that one grammar is ambiguous does not prove that its language has no unambiguous grammar. The two grammars here explicitly demonstrate the distinction.
Explore the fixed balanced-word examples below: the two rewrite orders describe one first-return tree, while two different trees within the ambiguous grammar witness ambiguity.
Why finitely many states cannot recognize all depths
Theorem 8.1.10
(The balanced words are not regular)
The language is not regular: no deterministic finite automaton recognizes it.
Proof
(Equal states, equal suffix, equal answer)
Suppose a DFA with states recognizes . Consider the prefixes consisting of opening parentheses, for . Two of them, with , must reach the same state.
Append exactly closing parentheses to both prefixes. The first resulting word has opening symbols followed by closing symbols and is balanced. The second has opening symbols but only closing symbols and is not balanced.
Starting from the same state and reading the same suffix forces the DFA to give the same acceptance result, a contradiction. Thus is not regular. The argument applies to every fixed finite number of states.
Proof X-ray
Where finiteness enters the collision argument
Finiteness is used exactly once, in the pigeonhole step: prefixes cannot reach distinct states. The non-obvious move is the order of choices. The prefixes of opening parentheses are fixed first, and the suffix is chosen only after the colliding pair is known, so that it depends on . The argument closes because the future of a DFA depends on its current state alone, and so equal states cannot separate from . Remove finiteness and the argument fails at once: a counter, which has unboundedly many values, separates all the prefixes .
For this single parenthesis type, a nonnegative unbounded counter can track unmatched openings. A pushdown automaton can represent the same quantity by stack height. This does not contradict the DFA argument: a counter or stack can grow with the input, while the number of DFA states is fixed. With multiple bracket types, matching the types requires additional information beyond the total height.
Recognize a word, or return its unique structure
The first function below checks the independent prefix definition. The second implements : None represents the empty production, while (inside, suffix) represents the two nonterminal children of . A returned None is therefore the valid parse of the empty word, not a failure value. Invalid words raise ValueError.
def is_balanced(text):
balance = 0
for symbol in text:
if symbol == "(":
balance += 1
elif symbol == ")":
balance -= 1
else:
return False
if balance < 0:
return False
return balance == 0
def parse_balanced(text):
position = 0
def parse_S():
nonlocal position
if position == len(text) or text[position] == ")":
return None
if text[position] != "(":
raise ValueError("expected opening parenthesis")
position += 1
inside = parse_S()
if position == len(text) or text[position] != ")":
raise ValueError("missing closing parenthesis")
position += 1
suffix = parse_S()
return (inside, suffix)
tree = parse_S()
if position != len(text):
raise ValueError("unmatched closing parenthesis")
return tree
Each terminal is consumed once, and each recursive call either consumes a pair or returns an empty subtree. Parsing takes linear time in the word length and linear worst-case tree and recursion space. This recursive teaching implementation is subject to Python's recursion limit for very long words. The iterative membership check avoids that recursion; its counter needs enough bits to represent the current depth, rather than a fixed finite set of states.
Worked example 8.1.11
(Running the parser on two invalid words)
Take ()). The call parse_S() at position consumes (; the inner call returns None at position because text[1] is ); the closing parenthesis is consumed, and the suffix call at position also returns None because text[2] is ). The tree (None, None) has been built, but position is while len(text) is , so the final check raises ValueError for an unmatched closing parenthesis.
Take ((). The outer call consumes the first (. The inner call consumes the second (, finds the ), and builds (None, None). Back in the outer call, position equals len(text), so the test for a closing parenthesis fails and ValueError reports a missing closing parenthesis. By contrast, parse_balanced("") returns None: this is the valid parse of the empty word, not an error.
Count words by the unique first-return split
Proposition 8.1.12
(Recurrence for balanced words)
Let be the number of balanced words with pairs. Then , and for the number is the sum, over , of .
Proof
(Counting by the unique first-return split)
Let be the number of balanced words with pairs. There is one empty word, so . In a nonempty word , if contains pairs, contains pairs. The decomposition is unique, so we neither omit nor double-count words:
This gives , , and , the beginning of the Catalan numbers.
Common mistake
(Counting words is not counting parse trees)
The recurrence counts words, not arbitrary derivations of . Counting ambiguous derivation trees instead would answer a different question.
Yes: the counts are the Catalan numbers, and each count is about four times the previous one.
A natural next question
Is there a formula for the counts?
Yes: the counts are the Catalan numbers, and each count is about four times the previous one.
The recurrence has the closed form , which can be proved by other methods. For instance and , matching the values above. The ratio approaches , so the number of balanced words grows roughly like , up to a polynomial factor.
Exercises and worked solutions
Quick check
(Check both balance conditions)
Which of , (()()), ())( and (() are balanced? For each rejected word, identify either a negative prefix or a nonzero final balance.
Solution · Answer
The empty word and (()()) are balanced. The prefix ()) of ())( has balance , even though the whole word ends at zero. The word (() never has negative balance but ends at 1, so one opening symbol remains unmatched.
Quick check
(Recover the unique decomposition and tree)
Find the first-return decomposition of (())(). Using None for an empty subtree and (inside, suffix) for a nonempty one, give the tree returned by the parser.
Solution · Answer
The first return is at position four, so the inside and suffix are both (). Each has tree (None, None). The complete tree is ((None, None), (None, None)), whose root describes the first outer pair and the remaining suffix.
Quick check
(Separate ambiguity from rewriting order)
After using in , two derivations expand the two nonterminals in opposite orders but eventually produce the same word and the same tree. Does this prove ambiguity? What kind of pair would prove it?
Solution · Answer
It does not prove ambiguity: the derivations merely schedule the same tree's expansions differently. One must exhibit two different parse trees for one word, or equivalently two different leftmost derivations. The unique first-return proof excludes such a pair for .
Quick check
(Exhibit a real ambiguity without changing the language)
For , describe two different root productions leading to (). Does that prove the balanced-word language has no unambiguous grammar?
Solution · Answer
One tree uses the enclosing production at the root and an empty inside. Another uses concatenation at the root, with () on the left and the empty word on the right. Their different root productions certify distinct trees. This proves ambiguous, but is an unambiguous grammar for the same language, so the language itself does have an unambiguous description.
Quick check
(Use a shared DFA state to force a contradiction)
Suppose prefixes with two and five opening parentheses reached the same DFA state. Which common closing suffix distinguishes their membership in the balanced-word language, and why must the DFA nevertheless give equal answers?
Solution · Answer
Append two closing parentheses. The first word is balanced; the second still has three unmatched openings. A DFA's continuation depends only on its current state, so equal states followed by the same suffix must yield equal acceptance results. It cannot correctly recognize both words.
Quick check
(Count words rather than ambiguous trees)
Use the recurrence to compute from . List the five words counted by . Why is this not a count of parse trees of ?
Solution · Answer
. The five three-pair words are ((())), (()()), (())(), ()(()) and ()()(). They are distinct terminal words. Grammar gives multiple trees even to the same word, including trees with extra empty concatenations, so its tree count would not equal this word count.