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.
