# Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?

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?

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

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?