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?

$\endgroup$
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.

$\endgroup$
  • $\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 '15 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 '15 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 '15 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 '15 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 '15 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.

$\endgroup$

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.