1
$\begingroup$

A Snippet of the proof from the bookIn Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation)does a PDA go on to compare two configurations and figure out that the first properly yields the second.

I know that the computation histories are encoded in a convenient manner (reversing), but I couldn't seem to figure out how and what the PDA really does.

Improve this question
$\endgroup$
4
  • $\begingroup$ What is "the mentioned language"? Please edit your question to make it self-contained. Please define all notation. How do your question about comparing two configuration relate to the first sentence of your post? $\endgroup$
    – D.W. ♦
    Apr 5, 2020 at 23:14
  • $\begingroup$ What is "ALL_CFG"? It would help to define this notation before using it. $\endgroup$
    – D.W. ♦
    Apr 7, 2020 at 17:57
  • 1
    $\begingroup$ The answer would be rather verbose to write. The idea is that you can check that the input is of the form $\#w\#w^R\#w\#w^R\# \ldots$, and you can extend this to have the various $w$'s slightly different, following the local computation rules of the Turing machine. Perhaps the original paper bothered to list all the details. $\endgroup$
    – Yuval Filmus
    Apr 7, 2020 at 18:00
  • 1
    $\begingroup$ A few more details are in Hendrik Jan's note (see Section 3). You can also check the original papers cited there. $\endgroup$
    – Yuval Filmus
    Apr 7, 2020 at 18:02

0

Reset to default

Your Answer

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