Let $G$ be a CFG, let $A$ be one of its non-terminals, and let $x$ be a string. Define the language = $ \{ \langle G,A,x\rangle|$there exists a derivation of $x$ in which $A$ is used $\}$. Is this language T-recognizable? Is it decidable?

Obviously, we can determine if there is at least one derivation for $G$, since context-free languages are decidable. But we cannot print every derivation. One idea could be to convert to Chomsky normal, and then print all possible derivations up to a certain length, but I am not sure if it would work.

Could one start with first designing a recognizer that is not necessarily decidable and then tweak it to be a decider?

  • $\begingroup$ So what is your question? Is it Recognizable? or Is it decidable? $\endgroup$ – fade2black Oct 12 '17 at 17:48
  • 1
    $\begingroup$ Hint: Think about the proof of the Pumping lemma. $\endgroup$ – Raphael Oct 12 '17 at 18:18

You are asking two different questions, I will answer only the first one.

Is this language T-recognizable?

Designing first recognizer and then transforming it into a decider will not always work. A language may be undecidable but recursively enumerable.

Your approach is correct. This language is recognizable (recursively enumerable). Just systematically generate all possible sentences (for example by breadth first search algorithm) every time by checking if any derivation contains the nonterminal $A$ and the derived sentence is $x$. If the test passes then ACCEPT.

A hint for the second question: $x$ has some certain length $n$. Can derivation of all sentences of length $n$ help us decide?

Also, a decidable language is also recursively enumerable, but the converse is not always true.

| cite | improve this answer | |

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.