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 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 are those whose strings are accepted by a

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.

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**:$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.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS