I am supposed to find an algorithm solving the following problem:

Given a CFG $ \;G=(V_N, V_T, R, S)$ and a nonterminal $ v \in V_N$ determine if there exists a production chain $ S \Rightarrow^* v \alpha$ , where $ \alpha = (V_N + V_T)^*$ .

Not sure if that’s the right term, but in other words we are trying to check if you can yield $ v$ from $ S$ – the starting symbol.

I don’t know anything about the form of the grammar and I can’t convert it into Chomsky’s form as it would introduce new nonterminals and possibly remove $ v$ . Where do I start with this? Any suggestions?

Thanks