CMSC 28000 — Lecture 25

Undecidable problems about context-free languages

There is a similar result characterizing undecidable properties of languages for subclasses of decidable languages (i.e. context-free languages, context-sensitive languages, etc.) called Greibach's theorem. As you might expect, this was shown by Sheila Greibach in 1963 (you may remember Greibach being mentioned when were talking about normal forms for grammars).

We won't prove Greibach's theorem, but we will show that some problems about context-free languages are undecidable. The proofs for these kinds of problems are going to be much trickier, since we don't have the benefit of conjuring up Turing machines. However, we can do something that may be surprising, which is make use of computations of Turing machines.

Let $M$ be a Turing machine and $w$ and input string. An accepting computation path for $M$ on $w$ is a sequence of configurations $C_1, \dots, C_\ell$, where $C_1$ is the start configuration of $M$ on $w$ and $C_\ell$ is an accepting configuration of $M$ on $w$ and each $C_i$ follows directly from $C_{i-1}$ (that is, $C_{i-1} \vdash C_i$) as defined by the transition function of $M$. We define a rejecting computation path similarly.

This gives us a very strict format for the computation of a word $w$ when run on a Turing machine $M$. We will show that we can compute all of the strings that aren't accepting computations.

Consider the language \[A(M,w) = \{\langle C \rangle \mid \text{$C$ is an accepting computation path for $M$ on $w$}\}.\] Then $\overline{A(M,w)}$ is a context-free language.

In order for a string to be an accepting computation for $M$ on $w$, it must satisfy the following conditions:

  1. $\langle C \rangle$ is a string of the form $\langle C \rangle = \# C_1 \# C_2^R \# C_3 \# C_4^R \# \cdots \# C_\ell \#$,
  2. $C_1$ is a starting configuration,
  3. $C_\ell$ is an accepting configuration,
  4. For each $C_i$, $C_i \vdash C_{i+1}$ according to $M$.

You might wonder why we're reversing every other configuration in our encoding of $C$. We will get to that shortly. However, we claim that for each of the items in the previous list, we can define a language $A_i$ for them. Then $$A(M,w) = A_1 \cap A_2 \cap A_3 \cap A_4,$$ which is all strings which satisfy all of our conditions. By De Morgan's laws, we have $$\overline{A(M,w)} = \overline{A_1} \cup \overline{A_2} \cup \overline{A_3} \cup \overline{A_4}.$$ Then, we must show that each $\overline{A_i}$ are context-free languages. The first three are easy: $A_1, A_2, A_3$ are actually regular, and it's not hard to see how you can define a DFA for each of those languages.

The not so obvious part is showing that $\overline{A_4}$ is context-free. Suppose that we have a string that satisfies conditions 1 through 3. To fail condition 4, we must find a substring $\#C_i\#C_{i+1}^R\#$ such that $C_i \not\vdash C_{i+1}$. Suppose we are using a PDA to do this. When reading $C_i$, we push every symbol of $C_i$ onto the stack. Then when reading $C_{i+1}^R$, we pop every symbol of the stack to compare.

Since our language is specific to $M$, we can compare the two configurations against the transition function of $M$. The crucial thing to notice here is that the change to the configuration by following a single transition of a Turing machine is very localized around the position of the tape head, and there are finitely many changes that one can make.

Then since each of $\overline{A_i}$ are context-free, their union, $\overline{A(M,w)}$, is also context-free.

We can now use this to show that universality for CFGs, is undecidable: $$U_{CFG} = \{\langle G \rangle \mid \text{$G$ is a CFG and $L(G) = \Sigma^*$} \}$$

$U_{CFG}$ is undecidable.

We will assume that $U_{CFG}$ is decidable and show that doing so will allow us to decide $A_{TM}$. Consider the language $\overline{A(M,w)}$ of strings that are not accepting computation paths for $M$ when run on $w$. Observe that $M$ accepts $w$ if and only if there is an accepting computation path $C$ for $M$ when run on $w$. So $C \in A(M,w)$ and therefore $C \not \in \overline{A(M,w)}$. Then $A(M,w) = \emptyset$ if and only if $M$ does not accept $w$, or equivalently, $M$ does not accept $w$ if and only if $\overline{A(M,w)} = \Sigma^*$.

Now, suppose we have a Turing machine, say $T$ that decides $U_{CFG}$. Then we can construct a Turing machine $S$ that decides $A_{TM}$ that does the following:

  1. On input $\langle M,w \rangle$, construct a context-free grammar $G$ for $\overline{A(M,w)}$, which we have shown is context-free by Lemma 25.2.
  2. Run $T$ on $\langle G \rangle$ to decide whether $L(G) = \Sigma^*$.
  3. If $T$ accepts, then reject. If $T$ rejects, then accept.

Since $A_{TM}$ is undecidable, we can conclude that $U_{CFG}$ is undecidable.

This gives us a very easy way to show that $EQ_{CFG}$ is undecidable.

$EQ_{CFG}$ is undecidable.

If we have a TM $R$ that decides $EQ_{CFG}$, then we can decide $U_{CFG}$ with the following machine:

  1. On input $\langle G \rangle$, where $G$ is a CFG, run $R$ on input $\langle G,G' \rangle$, where $L(G') = \Sigma^*$.
  2. If $R$ accepts, accept; if $R$ rejects, reject.

But $U_{CFG}$ is undecdiable, so $EQ_{CFG}$ must also be undecidable.

This technique of defining CFGs to generate Turing machine computations (or not Turing machine computations, as it turns out) was shown by Hartmanis in 1967. He shows that several other decision problems regarding CFGs are undecidable using the same approach.

Post's Correspondence Problem

Suppose we have a collection of dominoes. A domino is a tile that has a string on the top and a string on the bottom: $\binom{a}{ab}$. A collection of dominoes looks like $$ \left\{ \binom{b}{ca}, \binom{a}{ab}, \binom{ca}{a}, \binom{abc}{c} \right\}.$$ We want to find a match from a sequence of dominoes drawn from our collection: $$ \binom{a}{ab} \binom{b}{ca} \binom{ca}{a} \binom{a}{ab} \binom{abc}{c}.$$

An instance of the Post Correspondence Problem is a sequence of pairs of strings $$(u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)$$ where $u_i, v_i \in \Sigma^*, i = 1,\dots,k$. A solution of the above instance is the sequence $i_1,i_2,\dots,i_n \in \{1,\dots,k\}$ such that $$u_{i_1} u_{i_2} \cdots u_{i_n} = v_{i_1} v_{i_2} \cdots v_{i_n}.$$ The Post Correspondence problem asks whether or not a given instance of PCP has a solution. We define the language of PCP instances that have a solution to be $$L_{PCP} = \{ \langle P \rangle \mid \text{$P$ is a PCP instance that has a solution} \}.$$ Then we have the following result.

PCP is undecidable.