I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation,

"Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$. Use the computation history method to show that this problem is undecidable."

I have an attempt at a solution but somehow I just feel kind of foggy on whether it's correct and would appreciate anyone finding flaws in the solution.

For reference, I'm trying to mimic or adapt the solution given earlier in the chapter to

$$ ALL_{CFG}=\{\langle G\rangle | G \text{ is a CFG and } L(G)=\Sigma^*\}$$

Theorem: $ALL_{CFG}$ is undecidable.

The proof given there reduces from $A_{TM}$ the decision problem of checking whether a TM called $M$ accepts a string called $w$. It does so by, for any fixed $M,w$, constructing a CFG $G$ which produces all possible strings if and only if $M$ accepts $w$. In particular $G$ is the CFG which generates all the strings that are NOT accepting histories for $M$ on $w$.

It then proceeds to show how to build such a $G$. For the purposes of the problem I'm asking about, I can just accept that this is possible.

Also for reference, there is this answer to a similar question on here: https://cs.stackexchange.com/q/6629

I particularly want to follow the textbook's guidance in order to practice this method of using a computation history, so I'm ignoring the first answer to the problem. However, I don't understand the answer given for computation histories. The CFG that he gives (or equivalent PDA) doesn't seem to generate strings with at least one $v!v$ if and only if $M$ accepts $w$. Supposing $M$ accepts $w$ I don't see a reason why $C_0\#...\#m(C_{2n})\#C_f = C_1'\#...\#m(C_n')$.

My solution is, like in the book's solution for $ALL_{CFG}$, to try to use $M$ and $w$ to build a CFG such that $M$ accepts $w$ if and only if $G$ generates some string of the form $vv$. In particular $G$ is the grammar defined by the PDA $D$ which on input $x$ checks the first half to see if it's an accepting history of $M$ for $w$, and then checks the second half to see if it equals the first half. I believe each of these are things any PDA can do, and once built, $G$ will have the properties promised earlier. Am I making any mistake here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.