Theory of Computation (Automata)
What does Recursively enumerable language refer to?
- A. The sequence of production rule applications used to generate a string from a grammar's start symbol.
- B. A class of languages for which a Turing machine will accept and halt on strings in the language, but may not halt on strings outside it. ✓
- C. A finite sequence of symbols drawn from an alphabet.
- D. A finite-state machine whose output values are determined solely by its current state.
Correct answer
B. A class of languages for which a Turing machine will accept and halt on strings in the language, but may not halt on strings outside it.
Explanation
Recursively enumerable language refers to a class of languages for which a Turing machine will accept and halt on strings in the language, but may not halt on strings outside it.