# Decidable language: set of context-free langauges containing 1 string

ONE = {(G) : G is a CFG such that L(G) contains exactly one string} .

I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input. I am struggling at coming up with a high level definition.

My Possible Solution:

On input G, where G is a Context-free grammar, If non-terminal has more then one option that it can lead to, reject. Else accept.

• Your solution won't work: although there are different continuations they might lead to the same string. – Hendrik Jan Aug 11 '15 at 20:16
• An alternative to Yuval's approach can be found in this question – Ran G. Aug 12 '15 at 0:05
• What is your question? I see a bunch of declarative statements, but no question. If your question is "please tell me whether my solution is correct", the question is off-topic for this site: "please check my answer" questions are not likely to be useful to anyone else in the future and so are not a good fit for our focus. – D.W. Aug 12 '15 at 0:53

Hint: The point of this exercise is that it is decidable whether a context-free grammar generates the empty language. Using this as a black box, you can proceed as follows. On input $G$:
1. Check if $L(G)$ is empty, and if so, reject.
2. Find a word $w \in L(G)$.
3. Check whether $L(G) \cap (\Sigma^* \setminus w)$ is empty.
I'll let you figure out how to implement the latter two steps; step 2 uses the fact that it is decidable whether a grammar $G$ generates a given word $x$, and step 3 uses the fact that the intersection of a context-free language and a regular language is context-free (constructively).
The same idea can be used to calculate $L(G)$ given that we know that $L(G)$ is finite.