1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
1
$\begingroup$

Another "cool" way to prove it is realizing that there is an immediate reduction from the Post Correspondence Problem to the problem of checking wether a CFG grammar accepts a palindrome (or equivalently checking wether 2 CFG grammars accept the same string).

Given a PCP instance; i.e. a set of tiles

$\{ (x_i / y_i) \}$ (wher $x_i$ is the top string of the tile, and $y_i$ is the bottom string of the tile.

Simply build the CFG grammar $G$ with productions:

$\{ S \to AB\} \cup \{ A \to x_i A a_i \} \cup \{ B \to y_i B a_i \} \cup \{ A \to \epsilon \} \cup \{ B \to \epsilon \}$

where $a_i$ is a new unique terminal symbol that is associated with tile $i$

$G$ accepts a $ww$ string if and only if the original PCP problem has a solution.

And - of course - the undecidability of PCP proof uses the Halting problem and history of computation.

I found it myself after reasoning about a question on cstheory, but then I realized that it was not new :-); for further details see Post’s Correspondence Problem PCP is about context-free grammars.

$\endgroup$
2
  • $\begingroup$ @HendrikJan ... ops ... memory failed! ... fixed the answer. $\endgroup$
    – Vor
    Commented Dec 23, 2021 at 8:23
  • $\begingroup$ The rules of the form $\{A(B) \rightarrow \epsilon\}$ can cause problems and should be replaced with $\{A(B) \rightarrow x_ia_i(y_ia_i)\}$ $\endgroup$ Commented Nov 24, 2023 at 11:35

Your Answer

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

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