What are recursive languages?

The theory of computing defines two higher sets of languages: recursively enumerable and recursive. Recursively enumerable languages are the universal set of all the languages, and the remaining languages are their subsets.

Recursively enumerable languages

Recursively enumerable languages are those whose strings the Turing machine (TM) accepts. These strings may do one of the following:

• Halt and accept

• Halt and reject

• Loop forever

Turing machines for recursively enumerable languages may not always halt, and continue to run endlessly for strings that are not a part of that language. Recursively enumerable languages are also called Turing recognizing languages.

Recursive languages

Recursive languages are those whose strings are accepted by a total Turing machineA turing machine that always gives some input, i.e., it does not go into an infinite loop. that does either of the following:

• Halt and accept

• Halt and reject

A TM of a recursive language never goes into a loop and always halts in every case. Recursive languages are hence also called Turing decidable languages.

Note: To learn more about turing machines, we can click here.

Closure properties

Some closure properties of recursive languages are as follows:

• Union: The union of two recursive languages $L_1$ and $L_2$ is also a recursive language. This is, if the TM accepts any one of the languages, it also accepts $L_1 \cup L_2$.

• Intersection: The intersection of two recursive languages $L_1$ and $L_2$ is also a recursive language. This is, if the TM accepts both languages, it also accepts $L_1 \cap L_2$.

• Complement: The complement of a recursive language $L_1$ is also a recursive language. This is, if the TM accepts $L_1$, it rejects it as a final output.

• Kleene's closure: The Kleene's closure of a recursive language $L_1$ is also recursive. This is, if $L_1 = \{0^i1^j\}$ is recursive, then $L_1^* = \{0^i 1^j\}^*$ is also recursive.

Note: All recursively enumerable languages are recursive, but not vice versa.