Math and science::Theory of Computation

Examples of decidable and undecidable languages

Consider the decidability and recognizability of some specific languages. All the below languages represent answers to certain questions. If one of the languages is decidable, then the corresponding question can be answered definitively in finite time by a Turing machine.

The acronyms used below are:

DFA: Deteministic finite automaton
NFA: Non-deterministic finite automaton
CFG: Context free grammar
TM: Turning machine
Linear bounded machine: Linear bounded machine (TM with finite memory).

Given a DFA, $ B $, and a string, $ w $, does $ B $ accept $ w $?	$ A_{\text{DFA}} = \{ \langle B, w \rangle \| \text{$B$ is a DFA that accepts input string $w$} \} $	Decidable
Given a NFA, $ B $, and a string, $ w $, does $ B $ accept $ w $?	$ A_{\text{NFA}} = \{ \langle B, w \rangle \| \text{$B$ is a NFA that accepts input string $w$} \} $	Decidable
Given a CFG, $ G $, and a string, $ w $, does $ G $ generate $ w $?	$ A_{\text{CFG}} = \{ \langle G, w \rangle \| \text{$G$ is a CFG that generates input string $w$} \} $	Decidable
Given a TM, $ M $, and a string, $ w $, does $ M $ accept $ w $?	$ A_{\text{TM}} = \{ \langle M, w \rangle \| \text{$M$ is a TM that accepts input string $w$} \} $	Undecidable, but recognizable
Given a LBA, $ M $, and a string, $ w $, does $ M $ accept $ w $?	$ A_{\text{LBA}} = \{ \langle M, w \rangle \| \text{$M$ is a LBA that accepts input string $w$} \} $	Decidable!
Given a DFA, $ B $, is the language of $ B $ empty?	$ E_{\text{DFA}} = \{ \langle B \rangle \| \text{$B$ is a DFA and $\operatorname{L}(B) = \emptyset$} \} $	Decidable
Given a CFG, $ G $, is the language of $ G $ empty?	$ E_{\text{DFA}} = \{ \langle G \rangle \| \text{$G$ is a CFG and $\operatorname{L}(G) = \emptyset$} \} $	Decidable
Given a TM, $ M $, is the language of $ M $ empty?	$ E_{\text{TM}} = \{ \langle M \rangle \| \text{$M$ is a TM and $\operatorname{L}(M) = \emptyset$} \} $	Undecidable
Given a LBA, $ M $, is the language of $ M $ empty?	$ E_{\text{LBA}} = \{ \langle M \rangle \| \text{$M$ is a LBA and $\operatorname{L}(M) = \emptyset$} \} $	Undecidable
Given two DFAs, $ A $ and $ B $, do they recognize the same language?	$ EQ_{\text{DFA}} = \{ \langle A, B \rangle \| \text{$A$ and $B$ are DFAs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} $	Decidable
Given two CFGs, $ A $ and $ B $, do they recognize the same language?	$ EQ_{\text{CFG}} = \{ \langle A, B \rangle \| \text{$A$ and $B$ are CFGs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} $	Undecidable
Given two TMs $ M_1 $ and $ M_2 $, do they recognize the same language?	$ EQ_{\text{CFG}} = \{ \langle M_1, M_2 \rangle \| \text{$M_1$ and $M_2$ are TMs and $\operatorname{L}(M_1) = \operatorname{L}(M_2)$} \} $	Undecidable
Given a Turing machine, $ M $, does it halt on a given input?	$ HALT_{\text{TM}} = \{ \langle M, w \rangle \| \text{$M$ is a TM and accepts or rejects $w$} \} $	Undecidable
Given a Turning machine $ M $, does it recognize the same language as a DFA?	$ REGULAR_{\text{TM}} = \{ \langle M \rangle \| \text{$M$ is a TM and $\operatorname{L}(M)$ is a regular language.} \} $	Undecidable

Interesting point: the complement of $ A_{\text{TM} } $, $ \overline{A_{\text{TM} } } $, isn't even recognizable!

21.08.2021

Given a DFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)?	\( A_{\text{DFA}} = \{ \langle B, w \rangle \| \text{$B$ is a DFA that accepts input string $w$} \} \)	Decidable
Given a NFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)?	\( A_{\text{NFA}} = \{ \langle B, w \rangle \| \text{$B$ is a NFA that accepts input string $w$} \} \)	Decidable
Given a CFG, \( G \), and a string, \( w \), does \( G \) generate \( w \)?	\( A_{\text{CFG}} = \{ \langle G, w \rangle \| \text{$G$ is a CFG that generates input string $w$} \} \)	Decidable
Given a TM, \( M \), and a string, \( w \), does \( M \) accept \( w \)?	\( A_{\text{TM}} = \{ \langle M, w \rangle \| \text{$M$ is a TM that accepts input string $w$} \} \)	Undecidable, but recognizable
Given a LBA, \( M \), and a string, \( w \), does \( M \) accept \( w \)?	\( A_{\text{LBA}} = \{ \langle M, w \rangle \| \text{$M$ is a LBA that accepts input string $w$} \} \)	Decidable!
Given a DFA, \( B \), is the language of \( B \) empty?	\( E_{\text{DFA}} = \{ \langle B \rangle \| \text{$B$ is a DFA and $\operatorname{L}(B) = \emptyset$} \} \)	Decidable
Given a CFG, \( G \), is the language of \( G \) empty?	\( E_{\text{DFA}} = \{ \langle G \rangle \| \text{$G$ is a CFG and $\operatorname{L}(G) = \emptyset$} \} \)	Decidable
Given a TM, \( M \), is the language of \( M \) empty?	\( E_{\text{TM}} = \{ \langle M \rangle \| \text{$M$ is a TM and $\operatorname{L}(M) = \emptyset$} \} \)	Undecidable
Given a LBA, \( M \), is the language of \( M \) empty?	\( E_{\text{LBA}} = \{ \langle M \rangle \| \text{$M$ is a LBA and $\operatorname{L}(M) = \emptyset$} \} \)	Undecidable
Given two DFAs, \( A \) and \( B \), do they recognize the same language?	\( EQ_{\text{DFA}} = \{ \langle A, B \rangle \| \text{$A$ and $B$ are DFAs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \)	Decidable
Given two CFGs, \( A \) and \( B \), do they recognize the same language?	\( EQ_{\text{CFG}} = \{ \langle A, B \rangle \| \text{$A$ and $B$ are CFGs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \)	Undecidable
Given two TMs \( M_1 \) and \( M_2 \), do they recognize the same language?	\( EQ_{\text{CFG}} = \{ \langle M_1, M_2 \rangle \| \text{$M_1$ and $M_2$ are TMs and $\operatorname{L}(M_1) = \operatorname{L}(M_2)$} \} \)	Undecidable
Given a Turing machine, \( M \), does it halt on a given input?	\( HALT_{\text{TM}} = \{ \langle M, w \rangle \| \text{$M$ is a TM and accepts or rejects $w$} \} \)	Undecidable
Given a Turning machine \( M \), does it recognize the same language as a DFA?	\( REGULAR_{\text{TM}} = \{ \langle M \rangle \| \text{$M$ is a TM and $\operatorname{L}(M)$ is a regular language.} \} \)	Undecidable