Differentiate between recursive and recursively enumerable languages.


Recursive Language: Let L be a language over an input and if TM ‘T’ (Turing machine T) excepts every word in L and rejects every word of L^' it is called as recursive language.
Example:
(i) String ends with ‘101’
(ii) Number of ‘a’ = number of ‘b’
Accept (T) = L
Reject (T) = L'
Loop (T) = φφ
φ = null φ = null
Recursive languages are also called as Turing decidable languages.
A recursive language can be decided by Turing machine.
Recursively enumerable language: Let L be a language over an input, and if TM ‘T’ excepts every word of L and rejects or loops every word in L’ then it is called recursively enumerable language.
Example:
an bn
Accept (T) = L
Reject (T) + Loop (T) = L'
Recursively enumerable language are also called as Turing recognizable languages.
RE languages or type-0 languages are generated by type-0 grammars.


No comments

Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....

Theme images by ideabug. Powered by Blogger.