Why are the languages a pushdown automaton accepts closed under union but not under intersection?

Closure properties are the compact way of saying which ways of combining two accepted languages give you another one. For this class the pattern is lopsided, and the lopsidedness has a direct consequence for anyone building a validator out of two independent structural rules. ## Union: one decision, then never again Given two machines, build a third with a fresh start state and two moves out of it that consume no input, one into each machine's start configuration. A word is accepted if some run accepts it, so the new machine accepts exactly the words one of the originals accepts. The essential point is that the two branches are **alternatives**: only one of them ever touches the store in a given run, so the single store is never contended. The same construction in rule form is `S -> S1 | S2`, after renaming so the two rule sets share no nonterminals. Concatenation (`S -> S1 S2`) and repetition (`S -> S S1` with an empty alternative) work for the same reason. ## Intersection: two machines, one store The product construction that works for finite-state machines - run both in lock-step, with the state being a pair - fails here. Pairing the states is fine, since the control is finite either way. Pairing the **stores** is not: the model has one, and two independent last-in-first-out sequences cannot be interleaved into one and later drawn off separately. That is motivation rather than proof. The proof is a counterexample: 1. Let `L1` be the words `a^i b^i c^j` - the first two blocks equal, the third free. One store accepts it: match a's against b's, then consume the c's. 2. Let `L2` be the words `a^i b^j c^j` - the last two blocks equal, the first free. One store accepts it: consume the a's, then match b's against c's. 3. A word lies in both exactly when its first two blocks are equal **and** its last two blocks are equal, which forces all three to be equal. 4. So the intersection is `{a^n b^n c^n}`, which no stack machine accepts. Two members of the class whose intersection is outside it is exactly what non-closure means. ## Complement: settled by De Morgan The intersection of two languages is the complement of the union of their complements. The class is already closed under union; if it were also closed under complement, that identity would make it closed under intersection as well. Intersection fails, so **complement must fail too**. Worth stating in that direction: the argument runs from union plus complement to intersection, not the other way round. Note that the deterministic subclass behaves differently and **is** closed under complement - the failure here is a property of the full class. ## The exception that is genuinely useful Intersecting with a **regular** language stays inside the class. A finite-state machine has no unbounded memory, so its current state rides along inside the stack machine's finite control, and the pair advances together while the one store is used exactly as before. The result is another stack machine. | operation | stays in the class? | why | |---|---|---| | union | yes | one initial choice picks a machine; branches never share the store | | concatenation | yes | one rule set's start feeds the other's | | repetition | yes | a rule that re-enters the start symbol | | intersection | no | `a^i b^i c^j` with `a^i b^j c^j` yields three equal blocks | | complement | no | union closure plus complement closure would force intersection | | intersection with a regular language | yes | the finite-state machine's state rides in the control | ## What a validator author takes from this - 'Accepted by both rule sets' is **not** in general expressible as a third rule set. There may be no such rule set at all, so merging two grammars is not a technique. - A validator enforcing two independent structural constraints runs both readers and combines the verdicts, which means either two passes over buffered input or two readers driven over the same stream in parallel. - Layering a **regular** side-condition on top of a nesting-checked format is free in this sense: it can be folded into the reader's control without touching the store. - Because complement is not available, 'describe everything this format rejects' is not a request that always has a rule-set answer. A rejection story has to come from the reader, not from a second grammar.