Let $ G$ be a context-free grammar and $ w$ be a string of length $ |w| = n$ .

Consider the language $ A_{CFG}$ = { <$ G$ , $ w$ > | $ G$ is CFG that generates $ w$ }, where <$ G$ , $ w$ > is a string encoding of $ G$ and $ w$ .

Now we have to show that $ A_{CFG}$ is decidable, or in other words, there exists an algorithm that determines whether $ w$ is generated by $ G$ or not.

Now, the proof given in my book converts $ G$ into an equivalent CFG $ G’$ in Chomsky Normal Form and one-by-one checks all derivations in $ G’$ that take $ 2n – 1$ steps, since a grammar in CNF takes exactly $ 2n – 1$ steps to generate a string of length $ n$ .

Now, I have an alternate algorithm in mind. I want you guys to tell me if there is something wrong with it or not because this one seems to be much simpler than the one given in my book.

So, since every CFG has a pushdown automaton which recognizes the same language, we convert the CFG into an equivalent PDA. Now we simulate the PDA on our Turing machine on the string $ w$ . This process must end in a finite number of steps since our string is finite in length.

Is this an alternate algorithm that illustrates the decidability of $ A_{CFG}$ or is there something wrong with it?