2
$\begingroup$

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of

  • $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and
  • $\{G\mid G\text{ is a CFG and }L(G) = S\}$

decidable?

I know that the easier question of whether $D$ or $G$ generates a particular string $w$ or whether the language is the empty-language is decidable, but how can I decide on a particular set of strings?

I am thinking for the case of DFA I can do something like set-difference and check if $L(D/S)$ is empty.

For the case of CFG since it is not closed under complement is this question undecideable?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Let's assume that $S$ is regular and given in some explicit form (DFA, regular grammar, regular expression, what have you). Given a DFA $D$, we can compute a DFA for $L(D) \triangle S$ (here $\triangle$ is symmetric difference) and check whether it is empty or not. This allows us to decide whether $L(D) = S$ or not.

Given a CFG $G$, we can compute a CFG $G'$ for $G \cap \overline{S}$, and then check whether $L(G') = \emptyset$. This allows us to check whether $L(G) \subseteq S$. However, in general we cannot check the opposite inclusion: determining whether $L(G) = \Sigma^*$ is undecidable (the universality problem). However, if $S$ is finite, we can check whether $G$ generates each of the strings in $S$, and thereby solve the problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you build up further on the complement of S? Suppose S is a finite set containing strings. I want to see if L(G) = S. I first convert S into a CFG. I thought that CFGs are not closed under complement? $\endgroup$
    – John Smith
    Apr 23, 2015 at 2:12
  • $\begingroup$ Luckily, we are never complementing a CFG. I have assumed that $S$ is regular. We can complement regular languages and take their intersection with a CFG. $\endgroup$
    – Yuval Filmus
    Apr 23, 2015 at 2:24
  • $\begingroup$ Ahh I understand now. My final question is that I do not really see how I would intersect a CFG with a regular language. I understand all regular languages are context free. I'm just unsure of how I would perform this intersection. $\endgroup$
    – John Smith
    Apr 23, 2015 at 2:36
  • $\begingroup$ Convert the CFG to a PDA, use the product construction, and convert back. This only works for intersecting a CFG with a regular language, not two CFGs (the intersection of two context-free languages need not be context-free!). $\endgroup$
    – Yuval Filmus
    Apr 23, 2015 at 2:37
  • $\begingroup$ Ah ok, I didn't study PDAs so I wasn't sure how to approach this problem. $\endgroup$
    – John Smith
    Apr 23, 2015 at 2:51
2
$\begingroup$

If S is finite, then the answer is trivially "yes", for both questions.

If not, we have to know how it is (formally) defined. For instance, if it is defined by a Turing machine, then the answer is "no". In addition, the problem of equivalence of DFAs has a simple solution, but the equivalence of CFGs is undecidable.

Improve this answer
$\endgroup$

Your Answer

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

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