# Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

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?

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.

• 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? – John Smith Apr 23 '15 at 2:12
• 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. – Yuval Filmus Apr 23 '15 at 2:24
• 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. – John Smith Apr 23 '15 at 2:36
• 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!). – Yuval Filmus Apr 23 '15 at 2:37
• Ah ok, I didn't study PDAs so I wasn't sure how to approach this problem. – John Smith Apr 23 '15 at 2:51

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.