Recursive Language
For a given language if a turing machine can be designed which will halt on below 2 decisions:
- Whether String belongs to language
- Whether String does not belong to 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 languages are subset of Recursive Enumerable Langauges.Means: Every recusrive language is recursive enumerable language but vice-versa is not true.
Recursive Langauge Closure Properties
| Closure Property | Status |
|---|---|
| Union | Yes |
| Intersection | Yes |
| Set Difference | Yes |
| Compliment | Yes |
| Intersection with Regular Language | Yes |
| Concatination | Yes |
| Kleen Closure | Yes |
| Kleen Plus | Yes |
| Reversal | Yes |
| Homomorphism | No |
| ε-free Homomorphismx | Yes |
| Inverse Homomorphism | Yes |
| Substitution | No |
| ε-free Substitution | Yes |