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