# How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

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.

-
Sorry to ask a possibly silly question, but do you want to show that the language of such strings is not context-free? The acceptance problem for PDAs is decidable, an we can verify the structure of the input on TM no problem, so we can decide the language $\{\langle M,x\rangle\mid M \text{is a PDA and }x=w!w\}$. –  Luke Mathieson Nov 12 '12 at 6:03
A second though, is the language you mean to show undecidable $\{\langle M\rangle\mid M \text{is a PDA such that } \exists w \in \{0,1\}^{\ast} \text{ with } w!w \in L(M)\}$? –  Luke Mathieson Nov 12 '12 at 10:02
Hmm, it would be much easier if the form would be $\{ w!\overleftarrow{w} \mid w \in \{ 0, 1 \}^*\}$. With $w!w$ it is tricky. –  A.Schulz Nov 12 '12 at 10:32
@A. Schulz: With $w!w$ it can be done. The reversal parts can be inside the $w$'s. I invite you to read my answer. –  Hendrik Jan Nov 12 '12 at 10:36
@Raphael: From the wording, I at first thought he meant given $M$ and a string $x$ etc., but obviously the second formulation makes more sense. I was hoping to get a reply to clarify the question. –  Luke Mathieson Nov 12 '12 at 11:59
show 1 more comment

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.

-
Nice! Well, definitely more straightforward than my own solution. +1 –  Hendrik Jan Nov 12 '12 at 11:39
I find it hard to follow the flow of this answer. Why do you argue over existence of PDA/grammar in the third paragraph? If I read correctly, you want to map PCP instances to grammars, thus reducing the question to whether PCP is decidable. To that end, you also have to show the reverse of the last paragraph, namely that if no $u!u$ is accepted, the PCP has no solution. (Nice trick with the $t_i$, by the way.) –  Raphael Nov 12 '12 at 11:45
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.