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

Question

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.

Answer 1

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.

This is similar to the construction for deterministic finite state automata. The problem here is that the original PDA is not deterministic. Thus for a single input there might be two computations, one which accepts and the other that does not accept. With your construction both the original and the new PDA will accept that input.

Moreover there might be inputs that do not have a full computation (the machine "blocks"). With your construction both of the PDA will not accept.

PS. In his comment Raphael observes complementation for nondeterministic automata in general has the same flaw when one swaps accepting and nonaccepting states. Many of his links relate to Turing machines, but perhaps especially look at his own answer where the problem relates to finite automata: "Language described by inverting accepting states of NFA"