# 25+ Differences between recursive and recursively enumerable languages

 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

## FAQ about Recursive languages closure properties

Properties of Recursively enumerable languages

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.