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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2018 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$
    – John L.
    Dec 16, 2018 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$
    – John L.
    Dec 16, 2018 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$
    – John L.
    Dec 16, 2018 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, 2018 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.

Improve this answer
$\endgroup$
1
  • 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, 2018 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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