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

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