1
$\begingroup$

I've been asked to solve this problem, but I'm completely stuck now.

Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable?

I know I've to find a reduction, and as a hint they told me that it is related to Acceptance Problem or Post Correspondence Problem, or probably with Non-empty Intersection problem ( $\{\langle G1, G2\rangle \in \text{CFG} \times \text{CFG} \mid L(G1) \cap L(G2) \not= \emptyset\}$), which are undecidable.

I've been reading about these problems for hours, and reading about reductions from these problems to others trying to find any idea, but I'm stuck.

I'd really appreciate any help, whether some hints or the answer.

$\endgroup$
0
$\begingroup$

It depends on $A$.

As Hendrik pointed out, it is undecidable whether $L(G)\supseteq\Delta^∗$ for a context-free grammar $G$ with alphabet $\Delta$, $|\Delta|>1$: Is equivalence of a CFG and an RG undecidable?".

When the alphabet is unary, it is always decidable since a context-free language defined over a one-letter alphabet is regular and the problem of containment of regular languages is decidable.

It is trivially decidable whether $L(G)\supseteq\emptyset$ since the answer is always yes. In fact, it is decidable whether $L(G)$ contains a given finite language since the membership question for a context-free language is decidable because of CYK algorithm or any CFL parsing algorithm.

$\endgroup$
  • $\begingroup$ Sorry for my ignorance, but you say it depends on A but the you talk about the languate of the CFG G. Should I extrapolate all the cases for the language of G? I'm new in the world of computer science, so everything sounds a bit uncomprensible. Thank you! $\endgroup$ – sajunt4 Dec 15 '18 at 23:47
  • $\begingroup$ When I said $L(G)\supseteq\Delta^∗$, I meant to choose $A$ such that $L(A)=\Delta^*$. Since $\Delta^*$ is regular, it can be done. (For example, let $A$ be the DFA with a single state that is both the start state and the accept state.) Is it clearer now? $\endgroup$ – Apass.Jack Dec 16 '18 at 0:04
  • $\begingroup$ I am surprised that such a hard problem is given to a beginner. Or, can you double check whether your textbook has proved the undecidability of whether a context-free language contains $\Delta^*$? $\endgroup$ – Apass.Jack Dec 16 '18 at 8:16
  • $\begingroup$ If you do need to show that undecidability, you may consult more reductions and undecidable problems or Undecidable Problems for Context-free Grammars. $\endgroup$ – Apass.Jack Dec 16 '18 at 9:07
  • 1
    $\begingroup$ I've been reading my book, and I've found that it proves whether a context-free language contains the language of a DFA, but it says it's decidible for the subgrup of DPDA, but it doesn't prove that it's undecidable for the general case. Anyway, I really apreciate your interest and now I understand this much better. With that and all the info on the PDFs, I think I'll be able to solve the exercice! Thank you a lot! $\endgroup$ – sajunt4 Dec 16 '18 at 17:41
1
$\begingroup$

Indeed, it is undecidable whether a context-free grammar generates all strings over its alphabet. But I guess you want to know how such a result is obtained.

The classical result "undecidable $L(G) = \Delta^*$ for CFG $G$" was obtained by Bar-Hillel, Perles and Shamir in 1961 using a coding of Turing Machine computations. They showed that the set of strings that where not codings of valid TM computations form a context-free language. Of course if there are no valid computations then that language is $\Delta^*$.

You can do the same with codings of solutions of the Post Correspondence Problem. Given set of pairs $(u_1,v_1), \dots, (u_n,v_n)$ you can code PCP "solutions" as strings $u_{i_1}\dots u_{i_k}\#v^R_{i_k}\dots v^R_{i_1}$ such that both sides are equal (or rather, mirror image).

Argue that the non-solutions form a context-free language.

$\endgroup$
  • 1
    $\begingroup$ I'll try to compute this in my brain. English is not my main language and I'm new in Computer Science, so it could be hard jeje. Thank you! $\endgroup$ – sajunt4 Dec 15 '18 at 23:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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