Nesting and finite-state constraints
A context-free grammar can express recursive nesting, while a finite automaton can enforce a condition using finitely many states. Their intersection can enforce both requirements at once. This closure result is special: two arbitrary context-free languages need not have a context-free intersection. We will construct a grammar, including rules for empty words, and prove both directions of its meaning.
Let be a finite context-free grammar. Each production has one variable on the left and a finite sequence of variables and terminals on the right; the right side may be empty. A finite parse tree applies a production at each variable node, and its terminal leaves read from left to right form its yield. Let be a deterministic finite automaton with finite state set and total transition function . For a state and a word , write for the state reached by reading , with .
The goal is a grammar for : its words must have a grammar derivation and lead the automaton from to a state in . The construction does not require a special grammar normal form or an existing grammar-to-stack conversion.
Variables that remember entry and exit states
Definition 7.1.1
(Entry-exit variables)
For every and , introduce a variable . Its intended language consists of precisely those terminal words that can derive in and that move the automaton from to . Add a fresh start variable , with a rule for every . If is empty, has no such rules and the constructed language is empty.
Definition 7.1.2
(Compatible state sequences and the product rules)
For each original production , where each is a variable or a terminal, consider every sequence of states . A sequence is compatible when, for every terminal , the DFA transition satisfies . For every compatible sequence add
where when is a variable, and when it is a terminal. For an empty production , add for every , and no empty rule with different entry and exit states. Since and are finite and each right side has finite length, this produces finitely many rules, though the number may grow quickly with that length and .
Why the construction works
Lemma 7.1.3
(Meaning of an entry-exit variable)
For every , all and every terminal word , the variable derives in the constructed grammar if and only if derives in and .
Proof
(Induction on the height of parse trees)
First suppose derives by a finite tree. By induction on its height, its first rule came either from an empty production, so that and , or from an original production and a compatible sequence . Write , where is the yield of the th child. If is a terminal, then and compatibility gives . If is a variable, the child has a lower tree, so by the induction hypothesis derives in and . Hence in , and by composing the steps. In the empty case, is an original production and .
Conversely, suppose an original parse tree rooted at yields and . Split into the yields of the root's right-side symbols , a terminal contributing itself as a one-symbol piece. Set and ; these are the unique DFA states before and after each piece, and . For a terminal this gives , so the sequence is compatible and the root rule exists. For a variable , its subtree is lower and its yield moves to , so by induction derives . Attaching these derivations to the root rule gives . If , then and , and the explicit empty rule applies.
Proof X-ray
Where the DFA hypotheses enter
The key move is to let the grammar choose the intermediate states and let the word check them. The construction lists every state sequence for every production, so it guesses all possible intermediate states at once; the two directions of the lemma show that only the sequence the DFA actually follows can lead to a complete derivation.
Three hypotheses are used. Finiteness of makes the list of rules finite. Determinism and totality of give each word exactly one state sequence, which is why the converse direction can choose the root rule without ambiguity; for an NFA, compatibility would read and the lemma would say . The condition on empty rules is where the DFA's behavior on the empty word enters: reading does not move it.
The argument does not extend to two grammars. At a boundary, the information about a DFA is a pair of states from a finite set; the corresponding information about a second grammar would be a stack-like object of unbounded size.
Theorem 7.1.4
(Closure under intersection with a regular language)
Let be a context-free grammar and a DFA over the same alphabet. The constructed grammar with start variable generates exactly . In particular, the intersection of a context-free language and a regular language is context-free.
Proof
(Selecting the accepting exits)
The only rules for are with , so derives exactly when some with derives . By the lemma, this happens exactly when derives in and for some , that is, when and . If both sides are empty. The proof applies to finite derivation trees.
Concept lensStructural
Parse trees annotated with automaton states
A parse tree of the constructed grammar is an original parse tree of in which every variable node carries two labels: the state the DFA is in just before reading the node's yield and the state just after. Reading the leaves from left to right, the labels chain together: the exit state of one piece is the entry state of the next, and a terminal leaf leads from to . So the intersection grammar does not run the two machines side by side; it records the DFA's trajectory as a decoration on the parse tree.
Worked constraint: even nesting depth
Worked example 7.1.5
(Nested blocks with an even number of a symbols)
Take over with . It generates , with nested applications of the nonempty rule. Let a two-state DFA start in and accept , toggle on each , and leave its state unchanged on . It accepts exactly words containing an even number of symbols.
For , writing for the other state, the nonempty production yields
The empty production gives and ; the new start has the single rule . For example,
By the lemma, the grammar generates exactly . The empty word is included: both the original grammar and the DFA accept it, and .
Worked example 7.1.6
(Why ab is not generated)
The word belongs to , since , but the DFA rejects it. The rules for are and . To obtain , the first must be used, followed by . The only rule for is , and there is no empty rule with entry and exit . Hence is not derivable from .
Worked example 7.1.7
(A terminal in the last position, and an edge case)
Let have , generating . Let the DFA toggle on , stay on , start in and accept only . Compatibility gives for all , and, because must satisfy , only the rules and . The start rule is . Then
and . The word is not derived: it would need , which is not a rule because leaves the DFA in . The word is not derived either: after the variable is again, whose only rule starts with . The generated language is .
Common mistake
(An empty rule needs equal entry and exit states)
Adding with looks harmless but is wrong. In the even-nesting example, adding would give , so the grammar would generate , which has one and is rejected by the DFA. Reading the empty word never moves the DFA, so only is correct.
Limits and exercises
The construction assumes a DFA over the same alphabet; if a recognizer is given as an NFA, one may first determinize it. The theorem does not prove closure under intersection of two arbitrary context-free languages. Nor does the finite rule construction imply an efficient solution to every problem involving two grammars: it describes this finite translation for the stated inputs.
Counterexample mode
The same idea cannot intersect two context-free languages
Claim: if and are context-free, so is , by the same triple construction. Take , generated by , , , and , generated by , , . A word lies in exactly when and in exactly when , so . By the pumping lemma for context-free languages this language is not context-free; that standard fact is not proved here. The construction breaks because a triple summarizes a DFA's trajectory by two states from a finite set, whereas summarizing a second grammar's stack would need unbounded information. The theorem needs one of the two languages to be regular.
Quick check
(In the even-nesting example, trace the DFA states through and explain why the constructed start can derive it.)
Follow the DFA through the four symbols first.
Solution · Answer
The DFA goes on the four symbols and stays in on each , so it ends in the accepting state . The start derives the word: , the last step using .
Quick check
(If an original grammar has , explain why is allowed only when .)
What does reading the empty word do to the DFA state?
Solution · Answer
Reading leaves the DFA where it is, . A rule with would let derive although , contradicting the lemma. In the even-nesting example it would let derive .
Quick check
(Suppose . What does the fresh start derive? Explain why this agrees with the intersection.)
Look at which rules for exist.
Solution · Answer
There is no rule , so derives no word and the constructed language is empty. With no accepting state, , so as well.