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 proposed idea doesn't work, because after you have checked the first half of the input with your PDA, you have popped them all so you cannot reaccess them for comparing with the second half.

The correct idea should be making a PDA that checks if odd number configurations leads to even numbered configurations in the first half and vice versa in the second half. Also, make sure the PDA handles the start and accepting state. Then convert the PDA to CFG and pass it to the decider for the language $\{ww\}$. Accepts if it accept and rejects otherwise.

This will work as you can show that the PDA as constructed above will recognize string of form $ww$ iff $M$ accepts $w$. This is because the parity checks of configurations only gives incomplete information, but when supplied with the fact that you have two equal computation history in some string, it tells you each half of that string is actually an accepting computation history of $M$ on $w$.


Your Answer

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

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