|
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable one such as whether two context-free grammars accept the same language. However, I'm not sure how to use it as a subroutine. |
|||||||||||||||
|
|
So here is my approach: Show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is know to be not decidable. Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ you can build a sequence (incl. repetition) such that the concatenated $x_i$s and the concatenated $y_i$s of this sequence form the same word. Notice that the alphabet has to have at least 2 characters. There is a PDA that accepts a word in $L=\{ w!w \mid w \in \{ 0, 1 \}^*\}$, iff there is a context free-grammar that describes a word in $L$. It is a standard argument how to turn a context-free grammar into a PDA and vice versa. I use a grammar, since it is easier to set up for our purposes. Consider the context-free grammar, that has for the $i$-th element in $P$ a new terminal symbol $t_i$. We have the following rules: $$ \begin{align} S& \to X \; ! \;Y \\ X& \to x_1 X' t_1 \mid x_2 X' t_2 \mid \cdots x_n X' t_n \\ X'& \to x_1 X' t_1 \mid x_2 X' t_2 \mid \cdots x_n X' t_n \mid \varepsilon\\ Y& \to y_1 Y t_1 \mid y_2 Y t_2 \mid \cdots y_n Y t_n \mid \varepsilon \\ \end{align} $$ (The variable $X'$ is only there to rule out $S\Rightarrow !$). Assume now that $u!v$ is a word in this grammar. The words $u$ and $v$ have two parts, the suffix, consisting of the $t_i$ terminals, and the remainder called prefix. We have $u=v$, if and only if the prefixes and suffixes coincide. However, the suffixes coincide only if we have used the same sequence of tuples to built the words $u$ and $v$. The prefixes of $u$ and $v$ coincide, if the concatenation of the $x_i$s and $y_i$s (based on the reversed tuple-sequence given by the $t_i$s) is the same. Hence $u=v$, if and only if there is a solution for the encoded PCP instance. |
|||||
|
|
The approach might be as follows. Try to make a context-free (=PDA) language that codes computation steps of a TM, such that the complete computation is successful iff there is a word of the form you describe. First you need to code separate configurations: tape contents + state + position head (you will have seen that for grammar equivalence). A context-free language can encode a single step $C\vdash C'$ of a computatation provided you use mirror image $C\#m(C')$, where $m(C)$ denotes the mirror image (reversal) of $$C$. (I am sloppy here: you may have to distinguish configuration and its description.) Now consider the language of separate steps, concatenated with the language of duplicated configurations: $C_0\#C_1\#m(C_2)\#C_3\#m(C_4)\# \dots C_{2n-1}\#m(C_{2n})\#C_f!$ $C'_1\#m(C'_1)\#C'_2\#m(C'_2)\#\dots C'_{n+1}\#m(C'_{n+1})$ with for every $k$, $C_{2k-1} \vdash (C_{2k})$. This is context-free, additionally code $C_0$ as initial and $C_f$ as final configurations. Now the first part ensures we have consecutive steps, the second part that successive configurations are equal. If both parts match we have a computation. Which we cannot decide. That is the idea. I may have some indexes wrong, and the whole sequence has to be encoded in binary, but that can be solved. |
|||
|
