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:
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:
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:
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.
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.
First, let's talk about how we do this. The idea is to reduce from $A_{TM}$. We show that for any Turing machine $M$ and input string $w$, we can construct an instance of PCP such that a match is an accepting computation path for $M$ on $w$. Thus, if we have a match, then we can determine whether $M$ accepts $w$.
Suppose there is a TM $R$ that decides PCP. We construct a TM $S$ that decides $A_{TM}$. Let $M = (Q,\Sigma,\Gamma,\delta,q_0,q_A,q_R)$. We will have $S$ construct an instance of the PCP $P$ that has a match if and only if $M$ accepts $w$. Essentially, we will be defining pairs for the set $P'$.
First, we show how to do this with a restricted case of PCP where we require a particular starting pair. Later, we will show how to remove this restriction. The starting pair is defined $$\binom{\#}{\#q_0 w_1 w_2 \cdots w_n \#}.$$ Note that this is the starting configuration for $M$ on $w$.
Next, for every $a,b \in \Gamma$ and every $q,q' \in Q$ where $q \neq q_R$, if $\delta(q,a) = (q',b,R)$, add the pair $\binom{qa}{bq'}$. These pairs handle transitions for the tape head moving to the right.
For every $a,b,c \in \Gamma$ and every $q,q' \in Q$ where $q \neq q_R$, if $\delta(q,a) = (q',b,L)$, add $\binom{cqa}{q'cb}$. These pairs handle transitions for the tape head moving to the left.
For every $a \in \Gamma$, add $\binom a a$. These pairs correspond to tape contents that aren't near the tape head.
Add $\binom \# \#$ and $\binom{\#}{\Box\#}$. These pairs handle the delimiters between the configurations.
For every $a \in \Gamma$, add $\binom{a q_A}{q_A}$ and $\binom{q_A a}{q_A}$. This handles when the computation reaches the accept state. Note that the top lags behind the bottom, so we need to add some extra steps in order for us to get the match that we want.
Finally, we add the pair $\binom{q_A\#\#}{\#}$ to finish.
Now, we've constructed an instance $P'$ of PCP with a restriction, so it doesn't quite work the way we want it to. If we just use $P'$, there is a match regardless of whether $M$ accepts $w$ or not. So we have a bit more work to do.
First, let $w = w_1 w_2 \cdots w_n$ be some string of length $n$. Then we define the following strings:
Now, we convert our restricted PCP instance $P'$ that we constructed into a proper PCP instance $P$. If we have $$ P' = \left\{ \binom{u_1}{v_1}, \binom{u_2}{v_2}, \dots , \binom{u_k}{v_k} \right\},$$ where $\binom{u_1}{v_1} = \binom{\#}{\#q_0 w_1 w_2 \cdots w_n \#}$, then we define $P$ to be the set $$ \left\{ \binom{\star u_1}{\star v_1 \star}, \binom{\star u_1}{v_1 \star}, \binom{\star u_2}{v_2 \star}, \dots, \binom{\star u_k}{v_k \star}, \binom{\star \triangle}{\triangle} \right\}.$$
Then in the PCP instance $P$, the tile $\binom{\star u_1}{\star v_1 \star}$ is the only one that can be the first tile since it is the only one that starts with the same symbol $\star$. The addition of the $\star$s doesn't matter in the other tiles, since the $\star$s are simply interleaved in the original string. Then the final tile is always going to be $\binom{\star \triangle}{\triangle}$ to take care of the extra $\star$.
Post's Correspondence Problem originates all the way back from 1946, due to Emil Post. While we've shown that this is undecidable via Turing machine simulation, Post's original proof of undecidability uses the string generation system formulated by Post in 1943 which we've allueded to, the Post canonical systems. The languages generated by such systems are recognizable and so these systems are Turing-complete.
Of course, this isn't just a neat trick to show that there are undecidable problems that look deceptively easy. As with any undecidable problem, it can become another tool in our toolbox to show that a problem is undecidable. For instance, let's consider the problem of intersection emptiness for CFGs, $$ISE_{CFG} = \{ \langle G_1, G_2 \rangle \mid \text{$G_1, G_2$ are CFGs, $L(G_1) \cap L(G_2) = \emptyset$} \}.$$
$ISE_{CFG}$ is undecidable.
We assume that we can decide intersection emptiness for context-free languages. Let $\Sigma = \{a,b\}$ and we define $I$ to be an arbitrary PCP instance over $\Sigma$, $$(\alpha_1, \beta_1), \dots, (\alpha_k,\beta_k).$$ We define the following languages over the alphabet $\Sigma \cup \{c\} = \{a,b,c\}$.
All of these languages are context-free. Then we observe that $L_0 \cap L_{mi} \neq \emptyset$ if and only if $I$ has a solution. Since $L_0$ and $L_{mi}$ are context-free, if we could decide emptiness of the intersection of context-free languages, we can also decide whether or not an arbitrary instance of PCP has a solution.