3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

Pushdown automata are nondeterministic. Therefore you need to simulate all possible execution paths. The problem is that since PDAs support $\epsilon$-moves, there could potentially be infinitely many execution paths, and it's not clear whether there's an a priori bound on an accepting computation.

Using CFGs in Chomsky normal form circumvents all these difficulties.

Improve this answer
$\endgroup$
6
  • $\begingroup$ But isn't this also the case with an NFA. NFAs are also non-deterministic, but the NFA acceptance problem is decidable. $\endgroup$
    – Shashank Kumar
    Oct 23, 2019 at 9:40
  • $\begingroup$ The PDA acceptance problem is also decidable. It’s just not clear how to do it by simulation. $\endgroup$
    – Yuval Filmus
    Oct 23, 2019 at 9:47
  • $\begingroup$ A PDA can have epsilon transitions that do not read an input symbol but add something to the stack. So, you may have infinitely many possible stack contents before reading the next input symbol. However, in the case of an NFA, due to the absence of stack, there can only be a finite set of possible states before reading any input symbol, even after accounting for all possible epsilon transition paths. This difference between the types of epsilon transitions in NFA and PDA is the reason why an NFA can be simulated while a PDA cannot. Is this thought process correct? $\endgroup$
    – Shashank Kumar
    Oct 23, 2019 at 10:16
  • $\begingroup$ Right, that’s the idea. $\endgroup$
    – Yuval Filmus
    Oct 23, 2019 at 10:20
  • $\begingroup$ Also, you said that "it is not clear" how to do decide PDA acceptance by simulation. Not just that, I think it is actually impossible to decide the PDA acceptance problem by simulating the PDA. The reason is that if you could do so, then you would also be able to decide the problem of checking whether two CFLs are equivalent or not, which is undecidable. You could put one PDA after the other and accept only those strings that are accepted by exactly one of the PDAs. If the resulting language is empty then both CFLs are equivalent. But, this of course is an undecidable problem. $\endgroup$
    – Shashank Kumar
    Oct 23, 2019 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.