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$} \} $	[...]
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$} \} $	[...]
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$} \} $	[...]
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$} \} $	[...]
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$} \} $	[...]
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$} \} $	[...]
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$} \} $	[...]
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

01.07.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$} \} \)	[...]
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$} \} \)	[...]
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$} \} \)	[...]
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$} \} \)	[...]
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$} \} \)	[...]
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$} \} \)	[...]
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$} \} \)	[...]
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