# context free grammar not closed under relative complement using product construction of pda and dfa

Hello friends need a bit of help,

I Know that

given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$ because if it was contex free it would imply that $L_{cfg}$ is closed under complement and this is not true. But at another glance I can build a product construction of pda and dfa that could solve this problem.

Consider this:

1. product construction of pda and dfa

2. at any input read the input and at the same time move through the pda and the dfa

3. the accept states will be all the states where $(q_1, q_2)$ s.t $q_1\notin A_{pda}$ and $q_2\in A_{dfa}$

this machine should accept the language of $L_2/L_1$ and this would imply that this language is infect context free. I know that some-thing is wrong here but it scares me that I cant understand what... please help.

• – Raphael Feb 16 '18 at 11:16

If you forget about the product-part of this construction (or just consider $L_2=\Sigma^*$) then your proposal amounts to swapping the accepting states of the pushdown automaton. The new PDA has an accepting state iff the original one did not have one.
• There is a valid product construction of a PDA and a DFA. The only technicality is how to handle the $\varepsilon$-moves of the PDA. This will show the intersection of both languages. What will not work is swapping accepting and non-accepting states of the PDA to obtain its complement. For that one needs determinism. And even for deterministic PDA there is a technical problem: having to deal with infinite $\varepsilon$-computations. – Hendrik Jan Feb 15 '18 at 21:59