Automata

Recursive Language

For a given language if a turing machine can be designed which will halt on below 2 decisions:

  1. Whether String belongs to language
  2. Whether String does not belong to language
then that language will be recursive 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