Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Define the language INFINITEDFA ≡ { A | A is a DFA and L(A) is an infinite language}, where (A) denotes the description of the deterministic finite automata (DFA). Then which of the following about INFINITEDFA is TRUE:
1
It is regular.
2
It is context-free but not regular.
3
It is Turing decidable (recursive).
4
It is Turing recognizable but not decidable.