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