Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we learn about the properties of recursive and recursively enumerable languages in terms of *union*, *intersection*, and *complements* and compare the two languages.

### Table of contents.

- Introduction.
- Differences between recursive and recursively enumerable languages.
- Properties of both recursive and recursively enumerable languages.
- Summary.
- References.

## Introduction.

When a turing machine *T* operates on an input string *S*, there are three outcomes, these are;

- It halts and accepts the string.
- It halts and rejects the string.
- Never halts, proceeds infinitely.

**What are Recursive languages.**

We refer to a language *L* as recursive if there exists a turing machine *T* for it. In this case, the turing machine accepts every string in language *L* and rejects all strings that don't match the alphabet of *L*.

In other words, if string *S* is part of the alphabet of language *L*, then the turing machine *T* will accept it otherwise the turing machine halts without ever reaching an accepting state.

**Recursively enumerable languages.**

Here if there is a turing machine *T* that accepts a language *L*, the language in which an enumeration procedure exists is referred to as a recursively enumerable language.

Note that some recursive languages are enumerable and some enumerable languages are recursive.

The relationship between recursive and recursively enumerable languages.

Examples of recursively enumerable languages are;

Recursive languages, Regular languages, Context-sensitive languages, Context-free languages.

## Differences between recursive and recursively enumerable languages.

Factor | Recursive / Turing decidable languages) | Recursively enumerable / Turing recognizable languages) |
---|---|---|

Examples | Context-sensitive languages | RE languages. |

States | Halt-Accept, Halt-Reject | Halt-accept, Halt-Reject, Infinite Loop(No halting) |

Looping | Finite loops | Possibility of infinite loop |

Accept/reject | Accept (Turing machine) = L, Reject (Turing machine) = L, Loop (Turing machine) = ĻĻ, Ļ = null Ļ = null | Accept (Turing machine) = LReject (Turing machine) + Loop (Turing machine) = Lā |

## Properties of both recursive and recursively enumerable languages.

We will state theorems which are also properties of both languages.

- If language
*L*is recursive, its complement*L'*is also recursive.

*Proof:*

*L*is a language accepted by a turing machine that halts on all inputs. We construct a turing machine*Ts*from*T*as shown below:

We see that turing machine *T* given an input string *S* enters into an accepting state then *Ts* rejects and halts for string *W*. Also, if the turing machine *T* halts without accepting *W*, *Ts* enters into an accepting state. *Ts* accepts strings that are not accepted by *T*. Therefore, *Ts* recognizes the complement of *L*.

- If the languages
*L1*and*L2*are recursive, their union*L1 U L2*is also recursive.

*Proof:*

We have two turing machines*T1*and*T2*that recognize languages*L1*and*L2*. We construct a turing machine*T*as shown:

*T* simulates *T1* and *T* accepts input *S* is *T1* accepts it also. On the other hand, if *T1* rejects, *T* simulates *T2* and accepts if *T2* accepts.

Both *T1* and *T2* are algorithms and therefore they will halt at some point. We conclude that *T* accepts *L1 U L2*.

- The union of any two recursively enumerable languages is also a recursively enumerable language.

*Proof:*We have two recursively enumerable languages*L1*and*L2*that are accepted by turing machines*T1*and*T2*. We construct a turing machine*T*as shown below.

The machine simultaneously simulates *T1* and *T2* on separate tapes. If either accepts *S* then machine *T* also accepts *S*.

4, We have a language *L* and its complement *L'*, a recursively enumerable language. Then *L* will also be a recursive language.

*Proof:*

We have two turing machines *T1* and *T2* that recognize languages *L* and its complement *L'*. We construct a turing machine *T* as shown:

The machine *T* simulates *T1* and *T2* parallelly. States of *T1* and *T2* are components of the state of turing machine *T*. If *T1* accepts *S*, *T* accepts *S* also, if *T2* accepts *S*, *T* rejects *S*. This is so since *S* can either be part of *L* or part of *L'* therefore a single machine between *T1* and *T2* is expected to accept *S*.

From that, we learn that *T* will always accept or reject either but never both. Since *T* is an algorithm that accepts *L* we say that language *L* is recursive.

## Summary.

We have learned about the properties of recursive and recursively enumerable languages in terms of *union*, *intersection* and *complements*.

A language *L* as *recursive* if there exists a turing machine *T* for it. The turing machine accepts every string in language *L* and rejects all strings that don't match the alphabet of *L*

On the other hand, if there is a turing machine *T* that accepts a language *L*, the language in which an enumeration procedure exists is referred to as a *recursively enumerable language*.

With this article at OpenGenus, you must have the complete idea of Recursive and Recursively Enumerable Languages.