Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. This of course implies that $L_{REG}\le_m L_{CFG}$. Can anyone come up with natural, intuitive, direct reduction?

[I can give a reduction that goes through $L_{COF}=\{ \langle M \rangle : L(M)\text{ is cofinite}\}$, which is also complete for $\Sigma_3^0$. But it's not at all clear how to extract a direct reduction from the indirect one.]

  • $\begingroup$ I'd try to use the Chomsky–Schützenberger representation theorem but I'm not sure how yet. $\endgroup$ – xavierm02 Jan 31 '17 at 18:15
  • $\begingroup$ I don't see how the Chomsky–Schützenberger representation theorem is applicable here. $\endgroup$ – Aryeh Jan 31 '17 at 18:19
  • $\begingroup$ @Aryeh : You take your $L$ and feed it to your CFG-oracle. If it accepts, then you try to "complexify" the language in some way so that if it was regular it becomes context-free but if it wasn't, the result isn't context-free. Something like the ND defined in section 4.3 of www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf $\endgroup$ – xavierm02 Jan 31 '17 at 19:03
  • $\begingroup$ I don't understand what "take your $L$ and feed it to your CFG-oracle" means. $\endgroup$ – Aryeh Jan 31 '17 at 19:23
  • $\begingroup$ @Aryeh Don't mind that. I thought you had to check if the language is context-free first and then complexify it and test the complexified version (which you can do because by making the alphabets disjoint, you can test if two languages are CFLs by testing if their union is). But you may not have to. $\endgroup$ – xavierm02 Jan 31 '17 at 20:27

Your Answer

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

Browse other questions tagged or ask your own question.