patternMinor
Proving the decidability of whether a CFG generates a particular string or not
Viewed 0 times
generatesprovingthecfgdecidabilityparticularwhetherstringnot
Problem
Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.
Consider the language $A_{CFG}$ = { | $G$ is CFG that generates $w$ }, where 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?
Consider the language $A_{CFG}$ = { | $G$ is CFG that generates $w$ }, where 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?
Solution
If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.
So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. Since that word is not in the language your TM won't ever produce any output as simulation will never end. You were supposed to output a "NO" here.
On the other hand, the CNF algorithm works because it guarantees execution in finite steps for every word, whether it belongs to the language or not.
So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. Since that word is not in the language your TM won't ever produce any output as simulation will never end. You were supposed to output a "NO" here.
On the other hand, the CNF algorithm works because it guarantees execution in finite steps for every word, whether it belongs to the language or not.
Context
StackExchange Computer Science Q#116169, answer score: 4
Revisions (0)
No revisions yet.