Motivation
A regular constraint can check finite-state information while a pushdown automaton handles nesting or matching. Running the two machines in parallel gives a context-free language for their intersection. This useful closure property must not be confused with closure under intersection of two context-free languages: two independent unbounded matching requirements can exceed what a single stack can enforce.
The product construction below uses final-state acceptance after all input has been consumed. Silent pushdown moves leave the finite automaton's state unchanged. We then prove a concrete failure of intersection and complement closure for context-free languages.
Definitions
Definition 2.8.1
(Product of a pushdown automaton and a DFA)
Let be a nondeterministic pushdown automaton over finite alphabet , accepting by final state, and let be a complete DFA. A product configuration records the pushdown state and stack together with the current DFA state. If reads , the product advances by ; if takes an transition, the product leaves the DFA state fixed. A product state is final exactly when both component states are final.
Definition 2.8.2
(Context-free language)
A language is context-free if it is accepted by some nondeterministic PDA under this convention. The standard equivalence with context-free grammars is used here. Complement is taken relative to the fixed universe .
Theorems
Theorem 2.8.3
(Intersection with a regular language)
If is context-free and is regular over the same finite alphabet, then is context-free. If the PDA for is deterministic under the usual no-conflicting-silent-moves definition, the product remains deterministic.
Theorem 2.8.4
(Two context-free languages can have non-context-free intersection)
The context-free languages
have intersection , which is not context-free. Consequently context-free languages are not closed under intersection or complement.
Proof sketch or proof idea
Proof
(The product automaton recognizes the intersection)
In the product, a run projects to a run of and the unique DFA run on the symbols consumed so far. Induction on product transitions proves that the DFA component is exactly the state reached after the consumed prefix: an input move advances both components, and a silent move advances only . At the end, both machines have read the same complete word. The product accepts exactly when the PDA and DFA both accept it. The product has finitely many control-state pairs and uses the original stack alphabet, so it is a PDA.
If is deterministic, pairing its state with a DFA state adds no transition choices. The DFA transition is unique for each input symbol, and an move in the PDA still excludes input-reading moves for the same pushdown state and top symbol. Hence the product retains the deterministic condition. This proves closure under intersection with a regular language; it does not prove closure under intersection of two arbitrary deterministic pushdown languages.
Proof
(Two matching constraints cannot share one stack)
The grammar , , generates . Similarly , , generates . A word in both has the ordered form and satisfies and , giving the displayed intersection.
To show the intersection is not context-free, assume the context-free pumping lemma with pumping length and apply it to . In every permitted decomposition with and , the segment meets at most two of the three consecutive symbol blocks. Pumping down removes at least one symbol from or while leaving the count of at least one entire block unchanged. Deleting symbols from leaves a word of the form , so only the counts matter, and the three counts cannot all remain equal. This contradicts the pumping lemma.
Proof X-ray
Where the pumping argument uses its hypotheses
The word is chosen so that the bound forces the pumped segment to miss a whole block: the block alone has length . This is the one place the pumping length enters. Pumping down is chosen because deleting symbols keeps the block order and changes only counts. The hypothesis guarantees that some count really changes. The non-obvious move is to count the blocks that cannot touch, instead of tracking the symbols it does touch. The argument closes because an untouched block keeps its count while a touched block drops below , so the three counts cannot be equal, whichever allowed decomposition the lemma supplies.
Proof
(Complement closure would give intersection closure)
Context-free languages are closed under union by a grammar whose new start symbol chooses either grammar's start. If they were also closed under complement over , De Morgan's identity would give intersection closure. The counterexample rules this out, so complement closure fails as well.
Worked examples
Worked example 2.8.5
(Matching plus a parity condition)
Intersect with the regular language of words containing an even number of symbols. A DFA tracks parity while the PDA checks matching. The product accepts exactly .
Worked example 2.8.6
(Two different matching requirements)
The word belongs to because the numbers of and agree, but it is not in because the numbers of and differ. The word belongs to both. The intersection enforces both equalities simultaneously.
Worked example 2.8.7
(A pumped witness)
For , take and suppose the pumped pieces lie wholly inside the block, with at least one removed when pumping down. The numbers of and remain three while the number of symbols decreases. The resulting word is outside . The general proof covers every allowed placement, including a segment crossing one boundary.
Common mistakes
Counterexample mode
Regular is a real restriction
A tempting argument says: a PDA can be run in parallel with a DFA, so two PDAs can be run in parallel as well, and the intersection of two context-free languages is context-free. The languages and refute this. Each is context-free, by the explicit grammars above, and lies in both, yet their intersection is not context-free. The product with a DFA stores only finitely many extra states, whereas two PDAs would need two unbounded stacks, one comparing the symbols with the symbols and one comparing the symbols with the symbols, and a second stack is not part of the PDA model.
Common mistake
(Nonclosure does not make every intersection non-context-free)
Nonclosure means that at least one pair has an intersection outside the class; many particular intersections of context-free languages are context-free. Likewise, the complement argument is relative to a common alphabet and uses union closure. It does not identify the complement of every individual context-free language as non-context-free.
Constructing the product transition by transition
Let the PDA's control states be and its transition relation contain moves of the form , where is an input symbol or . The product control states are pairs . For an input-reading move, include
For a silent move include
The start state pairs the two start states, and the initial stack is unchanged. A product state is final precisely when is final for the PDA and is final for the DFA. These rules copy every PDA choice and add the single DFA update determined by the consumed symbol.
The product proof has two directions. Given a PDA run on a word, the DFA's unique run on that word determines the second component at each step, producing a product run. Conversely, projecting any product run onto its PDA component gives a valid PDA run, and its DFA component follows the correct input prefix by induction. Thus neither inclusion is assumed: every word in the intersection has an accepting product run, and every accepting product run witnesses membership in both languages.
Worked example 2.8.8
(A silent move does not change parity)
Suppose the DFA records whether the number of consumed symbols is even or odd. If the PDA takes a silent transition that pops a stack symbol while its DFA component is odd, the product remains odd. Only reading an flips the parity; reading or taking a silent move leaves it unchanged. Advancing the DFA on a silent move would assign a parity to a symbol that was never read.
The DFA must be complete for the displayed transition rule to be defined on every input symbol. A partial DFA can first be completed with a nonaccepting sink; this preserves its language under the usual convention that a missing transition rejects. If the two machines are presented over different alphabets, first specify a common alphabet and interpret missing symbols consistently. Otherwise even the complement universe or intended intersection may be unclear.
The pumping-lemma quantifiers
The context-free pumping lemma says that if a language is context-free, there is a pumping length such that every sufficiently long word in the language has some permitted decomposition with all pumped words remaining in the language. To derive a contradiction, choose a suitable long word and show that every permitted decomposition fails for at least one pumping exponent. Choosing one convenient decomposition and showing that it fails would not contradict the existential conclusion of the lemma.
For , a segment of length at most cannot contain both an and a : any such segment contains the entire intervening block of copies of plus at least one symbol from each neighboring block. Consequently at least one of the three symbol counts is untouched when and are removed. Since , at least one of the other counts decreases. The untouched count remains , so the three counts cannot all be equal. This argument covers the possibilities where the pumped pieces lie in one block or cross a single boundary; it does not need to list a separate decomposition for each position.
Common mistake
(Pumping is a necessary condition, not a characterization)
The pumping lemma provides a necessary condition for context-freeness, not a complete characterization. A language satisfying a pumping property for a particular decomposition or even for a proposed pumping length is not automatically context-free. In this proof the contradiction comes from the universal analysis of all decompositions allowed by the lemma for the chosen word.
Intersections and complements
For a fixed finite alphabet, the class of context-free languages contains the empty language and and is closed under finite union. To combine two grammars for union, first rename their variables so they are disjoint, introduce a fresh start variable and let it choose either old start. Variable renaming prevents a production from one grammar from accidentally expanding a variable belonging to the other. This construction accepts the union, not the intersection: the initial choice follows one grammar at a time.
The De Morgan step is a proof by contradiction about a class property. If every context-free language had a context-free complement, both complements in the formula would be context-free. Union closure would make their union context-free, and complement closure again would make the intersection context-free. Since the explicit intersection is not context-free, the assumed universal complement closure cannot hold. The argument guarantees that some context-free language has a non-context-free complement, but it does not by itself determine which of the two intermediate complements provides a particular witness.
Worked example 2.8.9
(A regular filter can preserve a simpler intersection)
Let , a regular language. Both and are already subsets of , so intersecting either one separately with leaves it unchanged and context-free. This does not imply their intersection with each other is context-free. The product theorem permits one context-free language and one regular filter at a time; it cannot be applied to the second language unless that language is known to be regular.
Acceptance and deterministic scope
The construction preserves final-state acceptance because it checks both final control states after the entire input has been read. If a PDA is originally presented with empty-stack acceptance, first use a valid conversion to the convention being used, or restate and prove the product for that convention. For deterministic machines, acceptance conversions require particular care: an added nondeterministic cleanup choice can violate determinism. The deterministic product claim here begins with a deterministic final-state machine and does not rely on such a conversion.
A DFA component adds no unbounded memory: there are only control-state pairs and the product has one copy of the PDA's stack. This is why the construction stays within the PDA model. A second arbitrary stack would be a different machine model, so the intuitive statement that two PDAs can simply be run in parallel is not a proof of context-free intersection closure.
Common mistake
(The two operands of the counterexample are context-free)
The nonclosure witness does not assert that either or is non-context-free; explicit grammars establish the opposite. It is the need to satisfy both matching constraints in their intersection that produces the non-context-free language. This distinction is useful when designing reductions: show membership of the operands in the claimed class before using their combination to refute a universal closure property.
Summary
A DFA can be combined with a PDA by storing its finite state in the control and updating it only on consumed symbols. Two context-free matching languages can intersect in , proving that unrestricted context-free intersection and complement closure fail.
Exercises
Quick check
(In the product construction, what happens to the DFA state during a PDA silent move?)
Compare what a silent move consumes with what advances the DFA.
Solution · Answer
It stays unchanged because no input symbol was consumed.
Quick check
(Is in ? Is it in ?)
Count the , and symbols against the definitions of and .
Solution · Answer
It is not in : there are two symbols and three symbols. It is not in : three symbols and zero symbols differ.
Quick check
(Why can a segment of length at most not meet all three blocks of ?)
Which block lies between the block and the block?
Solution · Answer
Meeting both the and blocks requires traversing the entire intervening block and at least one symbol on each side, a length greater than .
Quick check
(What closure property besides complement is used in the De Morgan argument?)
Which operation combines two grammars into one?
Solution · Answer
Closure under union, together with a common complement universe, yields closure under intersection by De Morgan's identity.