Recursive Enumerable Language

For a given language if a turing machine can be designed then that language will be recursive enumerable language.

Halting Problem

If turing machine answers YES for string belonging to language.
But for string not belonging to language Turing Machine can either answer NO or it could go into infinite loop.
Then this is called Halting problem and such a language is called Recursie Enumerable Language.
Below picture will put more light on the explanation:

In above pic the outer rectangle is Σ*(all possible strings over given input) and langauge is a subset of it.

Recursive Enumerable and Recursive Langauges

Recursive Enumerable languages are superset of Recursive Langauges.
Means: Every recusrive language is recursive enumerable language but vice-versa is not true.



Recursive Enumerable Langauge Closure Properties

Closure Property Status
Union Yes
Intersection Yes
Set Difference No
Compliment No
Intersection with Regular Language Yes
Concatination Yes
Kleen Closure Yes
Kleen Plus Yes
Reversal Yes
Homomorphism Yes
ε-free Homomorphismx Yes
Inverse Homomorphism Yes
Substitution Yes
ε-free Substitution Yes