Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 10 down vote accepted

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 $S\Rightarrow !$).

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.

share|cite|improve this answer
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
@Raphael, I edited the answer to address your comment. Good points -- thank you! – D.W. Dec 23 '13 at 19:25

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.

share|cite|improve this answer
Okay I got it. However the part "Now consider the language of separate steps, concatenated with the language of duplicated configurations ..." could profit from further explanations. For example, you could use the correct indices. Anyway, its a nice idea. – A.Schulz Nov 12 '12 at 10:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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