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

Problem Detail: 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.

Asked By : David Faux

Answered By : A.Schulz

Here is my approach: I’ll show that if you can decide your problem, then you can decide Post’s correspondence problem (PCP), which is known 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. So, let $P$ be an instance of the PCP. Consider the following context-free grammar, where we’ve introduced a new terminal symbol $t_i$ for the $i$-th element in $P$. The grammar has 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 $SRightarrow !$). Of course, given any grammar, we can find a corresponding PDA that accepts the same language as the grammar. So, construct the corresponding PDA, and then use the hypothetical algorithm for your problem to determine whether this PDA accepts any word of the form $u!v$ (i.e., whether one can derive any word of the form $u!v$ from this grammar). I will show how to use this information to solve the PCP instance $P$. Assume now that $u!v$ is a word in this grammar. The word $u$ has two parts, the suffix, consisting of the $t_i$ terminals, and the remainder called prefix. The same is true of $v$. We have $u=v$ if and only if their prefixes and suffixes coincide. The suffixes coincide only if we have used the same sequence of tuples from $P$ 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 PCP instance $P$. Similarly, if there is a solution for the PCP instance $P$, then from the solution it is easy to construct a word of the form $u!v$ that is derivable from this grammar. It follows that the PCP instance $P$ has a solution if and only if this grammar contains a word of the form $u!v$. If there was an algorithm to decide your problem, we could use it to solve PCP. But of course PCP is known to be undecidable, so your problem is undecidable, too.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6626