25+ Differences between recursive and recursively enumerable languages

By Prof. Fazal Rehman Shamil
Last modified on March 3rd, 2022
Comparison Recursive Language Recursively enumerable language
Also Known as Turing decidable languages Turing recognizable languages
Definition In Recursive Languages, the Turing machine accepts all valid strings that are part of the language and rejects all the strings that are not part of a given language and halt. In Recursively enumerable languages, the Turing machine accepts all valid strings that are part of the language and rejects all the strings that are not part of the given language but do not halt and starts an infinite loop.
States (1)   Halt and accept

(2)   Halt and Reject

 

(3)   Halt and accept

(4)   Halt and Reject

(5)   Never Halt (Infinite loop)

Loop Finite Loop Infinite loops of machine are possible
Halting Halting Turing Machine Non Halting Turing Machine
Accept/ Reject Accept (Turing machine) = L
Reject (Turing machine) = L
Loop (Turing machine) = φφ
φ = null φ = null
Accept (Turing machine) = LReject (Turing machine) + Loop (Turing machine) = L’
Closed under Closed under all except homomorphism, substitution, GSM mapping, and rational transduction Closed under all except set difference, and complementation.
context-sensitive language RE languages or type-0 language
Difference between recursive and recursively enumerable languages
Difference between recursive and recursively enumerable languages

FAQ about Recursive languages closure properties

Properties of Recursively enumerable languages

Recursive languages VS recursively enumerable languages in tabular form
Recursive languages VS recursively enumerable languages in tabular form
  1. Recursive Languages Closed Under union.
  2. Recursive Languages Closed Under intersection.
  3. Recursive Languages Closed Under set difference.
  4.  Recursive Languages Closed Undercomplementation.
  5. Recursive Languages Closed Under intersection with a regular language.
  6. Recursive Languages Closed Under concatenation.
  7. Recursive Languages Closed Under Kleene star.
  8. Recursive Languages Closed Under Kleene plus.
  9. Recursive Languages Closed Under reversal.
  10. Recursive Languages Closed Under λλ-free homomorphism.
  11. Recursive Languages Recursive Languages Not Closed Under homomorphism.
  12. Recursive Languages Closed Under inverse homomorphism.
  13. λλ-free substitution Recursive Languages Closed Under λλ-free substitution.
  14. Recursive Languages Not Closed Under substitution.
  15. Recursive Languages Closed Under λλ-free GSM mapping.
  16. Recursive Languages Not Closed Under GSM mapping.
  17. Recursive Languages Closed Under inverse GSM mapping.
  18. Recursive Languages Not Closed Under rational transduction.

 

FAQ about Recursively Enumerable languages closure properties?

  1. Recursively enumerable languages Closed under union.
  2. Recursively enumerable languages Closed under intersection.
  3. Recursively enumerable languages Not Closed under set difference.
  4. Recursively enumerable languages Not Closed under complementation.
  5. Recursively enumerable languages Closed under intersection with a regular language.
  6. Recursively enumerable languages Closed under concatenation.
  7. Recursively enumerable languages Closed under Kleene star.
  8. Recursively enumerable languages Closed under Kleene plus.
  9. Recursively enumerable languages Closed under reversal.
  10. Recursively enumerable languages Closed under λλ-free homomorphism.
  11. Recursively enumerable languages Closed under homomorphism.
  12. Recursively enumerable languages Closed under inverse homomorphism.
  13. Recursively enumerable languages Closed under λλ-free substitution.
  14. Recursively enumerable languages Closed under substitution.
  15. Recursively enumerable languages Closed under λλ-free GSM mapping.
  16. Recursively enumerable languages Closed under GSM mapping.
  17. Recursively enumerable languages Closed under inverse GSM mapping.
  18. Recursively enumerable languages Closed under rational transduction.

 

Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.