Undecidable Problems for CFGs

We currently know the decidability of the following problems:

Decidable	Undecidable
DFA $M$ accepts $w$	TM $M$ accepts $w$
CFG $G$ generates $w$	TM $M$ halts on $w$
DFAs $M$ and $M’$ accept the same inputs	TM accepts some input
	TM $M$ and $M’$ accept the same inputs

Computation Histories as Strings

If $M$ halts on “w”, the computation history of $(M,w)$ is the sequence of configurations $C_1,\ldots,C_i$ that $M$ goes through on input $w$.

The computation history can be written as a string hist over alphabet $\Gamma\cup Q\cup\{\#\}$:

Consider the following CFG:

\[\text{ALL}_\text{CFG}=\{\langle G\rangle\vert G\text{ is a CFG that generates all strings}\}\]

This language is undecidable.

We can argue that if $\text{ALL}_\text{CFG}$ is recursive, then so is $\overline{A_\text{TM}}$.

graph LR
m["(G)"] --> A
A -->|if G generates all strings| accept
A -->|if not| reject

flowchart LR
m["(M,w)"] --> c
subgraph S
c[construct G] -->|"(G)"| A
end
A -->|if M rej/loops w| accept
A -->|if M accepts| reject

…

I’m not too sure about what the method is completing in this example. Ask about slide 137 if it comes up in the tutorials.