## 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 |