Recursive Language
44/45
Gist: Recursive Language accepts TM that
always halt
Illustration:
Definition: Let L be a
language. If L = L(M), where M is DTM
that always halts, then L is a recursive language.
Theorem: The family of recursive languages is closed under complement.
Proof: See page 693 in
[Meduna: Automata and Languages]
Theorem: The family of recursively enumerable languages is not
closed under complement.
Proof: See the LSelfAcceptance