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?