COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
a) Recursive Ennumerable
|
|
|
b) Recursive
|
|
|
Both (a) and (b)
|
|
|
None of the mentioned
|
Detailed explanation-1: -Explanation: The language accepted by Turing machines are called recursively ennumerable (RE), and the subset of RE languages that are accepted by a turing machine that always halts are called recursive.
Detailed explanation-2: -Acceptor Turing Machine is an automaton used to define Turing-acceptable languages. Such a machine can be used to check whether a given string belongs to a language or not. It is defined as a 7-tuple machine. Coming to Transducers: In general, transducers are the devices used to convert one form of signal into another.
Detailed explanation-3: -Recursive languages are also called decidable. The concept of decidability may be extended to other models of computation. For example, one may speak of languages decidable on a non-deterministic Turing machine.
Detailed explanation-4: -The Universal Language L We have seen one language, the diagonalization language, that is not accepted by any Turing machine. This proves the diagonalization language is not recursively enumerable.
Detailed explanation-5: -Let M be a Turing machine. M accepts a string w if it enters the accept state when run on w. M rejects a string w if it enters the reject state when run on w. M loops infinitely (or just loops) on a string w if when run on w it enters neither the accept or reject state.