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.

  • $\begingroup$ Your solution won't work: although there are different continuations they might lead to the same string. $\endgroup$ – Hendrik Jan Aug 11 '15 at 20:16
  • $\begingroup$ An alternative to Yuval's approach can be found in this question $\endgroup$ – Ran G. Aug 12 '15 at 0:05
  • $\begingroup$ 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. $\endgroup$ – 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.


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.