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.


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"

  • $\begingroup$ Great thanks for the answer... So is there a way to construct a functioning product construction of Pda and dfa or should I avoid this kind of ideas in the future? I mean will this constriction work for let's say intersection of regular and context free grammar? $\endgroup$ – misha312 Feb 15 '18 at 15:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Feb 15 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.