Reformulating the Given Conditions in Decidability Problems

Question

I came across the following question:

Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ?

The problem $ALL_{\text{CFG}}$ that states:

Given a CFG $G$ then $L(G) = Σ^*$ is known to be undecidable.

So I thought to fix $L_2$ to be $Σ^*$ and allow $L_1$ to be any context-free language to prove that the problem stated is undecidable.

What concerns me the most is that the $ALL_{\text{CFG}}$ refers to a context-free grammar and not a context-free language.

One of the definitions of a context-language is the following:

$L$ is a context-free language $\leftrightarrow$ There exists a context-free grammar $G$ s.t $L(G) = L$ which translates to 2 things:

1. $L$ is a context-free language $\rightarrow$ There exists a context-free grammar $G$ s.t $L(G) = L$

2. Given a context-free grammar $G$ s.t $L(G) = L$ $\rightarrow$ $L$ is a context-free language

The only way I see to address my concern regarding $ALL_{\text{CFG}}$ is to add bullet $(1)$ to the proof and state that if the problem in question is decidable then $L(G_1) = Σ^*$ is decidable (which is not) where $G_1$ is the context-free grammar that generates $L_1$. Would this approach work?

I am seeing this kind of question for other kinds of languages as well.

Say that the problem in question was the following:

Given two recursive languages $L_1$ and $L_2$ is the $X$ problem decidable?

Will the same approach work if I manage to take the problem from the domain of recursive languages to the domain of Turing Machines with $M_1$ and $M_2$ where $L(M_1) = L_1$ and $L(M_2) = L_2$?

Answer 1

Your approach is correct.

---

Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ?

It is understood the $L_1$ is given as $L(G_1)$ where $G_1$ is a given context-free grammar. $L_2$ is given as $L(G_2)$ where $G_2$ is a context-free grammar.

This convention is used for similar propositions/exercises unless specified otherwise.

For example, if we are asked "given two recursive languages $L_1$ and $L_2$ is the $X$ problem decidable?", then we can assume $L_1$ is given by $L(M_1)$ where $M_1$ is a decider and $L_2$ is given by $L(M_2)$ where $M_2$ is a decider.

Technically, "a context-free language $L_1$" can be for example given as $L(S)$ where $S$ is a context-sensitive grammar such that $L(S)$ is context-free or given as $L(T)$ where $T$ is a Turing machine such that $L(T)$ is context-free. However, these kinds of interpretations are not used anywhere during introductory study.

---

Here is an exercise.

Prove the following promise problem is undecidable.
Given a Turing machine $T$ that accepts a decidable language and a string $w$, determine whether $T$ accepts $w$.

Here we should understand that it is possible the given $T$ is not a decider., although $T$ accepts a decidable language.

This undecidability says there is no decider that given an arbitrary string $w$ and an arbitrary semi-decider $S$ that accepts a decidable language, can output whether $S$ accepts $w$. In other words, the halting problem is still undecidable even the Turing machine in the input is guaranteed (by an oracle) to accepts a decidable language each time (however, it is possible that the given Turing machine itself is not a decider).