Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 05

Year:May 16

A language is recursive if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language.

for example lets take Turing machine M and String w: if string w is a member of the Turing machine M, then M halts in its final state otherwise it rejects the computation. ==>==> A language is recursive enumerable if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language may be loop forever.

for example lets take Turing machine M and String w: if string w is in the language , then M halts in its final state. Otherwise it rejects the computation or may be run forever

Recursive languages are decidable by some Turing Machine, i.e., there is a TM that can, given any input string (over the appropriate alphabet) correctly answer yes if the string is in the language, or no if it isn't.

A language is recursive enumerable if there exists a TM that keeps outputting strings that belong to the language (and only such strings), such that eventually every string in the language will be in the output.

Recursively enumerable languages are only recognized, i.e., there exists a Turing Machine that accepts when the string is in the language but it may loop forever if the string is not in the language.

Recursively enumerable Turing machine if it not accepts a string may halt in non final state or loop for ever which is not the case for recursive languages