Recursively Enumerable Languages

The most general class of languages processed by automata are the recursively enumerable (RE) languages—those that are recognized by a Turing machine. There are important subcategories within the RE languages that we’ll also explore. Most languages of practical use are in the subset of RE languages known as recursive languages. We’ll also lift all restrictions on rewriting systems to obtain grammars that generate the recursively enumerable languages.

Definition of recursively enumerable languages

A recursively enumerable language is a language that has an associated Turing machine that recognizes all and only the strings in the language. It may “hang” (run forever) when given an input string which is not in the language.

The term “recognized” is crucial. A $\text{TM}$ recognizes an input string if it halts in an accepting state when processing it. The set of all such strings constitutes the language of the $\text{TM}$. If an input string is not in the language, the $\text{TM}$ may (rarely) halt and reject it, or it may (more likely) get stuck in an infinite loop (“hang”). In other words, it knows one when it sees one, but it can’t always tell when a string is not in the language. This is a consequence of the fact that $\text{TM}$s do not always halt. All the languages that we have seen so far are recognized by $\text{TM}$s that always halt (i.e., they are decided by the $\text{TM}$). We must do a bit of work to contrive a language that is RE but not recursive.

Definition of a recursive language

A recursive language is a language that has an associated $\text{TM}$ that decides all input strings. The machine always halts, explicitly accepting all the strings in the language and rejecting those not in the language.

In other words, there is an algorithm that decides whether or not any given string is in a recursive language. We say that the $\text{TM}$ “decides” the language, instead of just “recognizing” it.

Remember: A recursively enumerable language has a Turing machine that recognizes it (it may hang on strings outside the language). A recursive language has a Turing machine that always halts, deciding each string.

Since a recursive language’s $\text{TM}$ recognizes each string in the language, recursive languages are recursively enumerable by default and form a proper subset of the RE languages.

A nonrecursive, RE language

To get a “feel” for a RE-but-not-recursive language, let’s suppose we just made a public post on social media. Now let’s consider the language consisting of the handle (username, email, or some other unique identifying string) of all the persons who will at some point respond to that post. Notice the future tense here. If we’re given an arbitrary handle for some user of the same social medium, we might wait forever to see if they respond. We can only know about those who have responded already. This language of handle strings is not “decidable” because of the way it is defined.

Context-sensitive languages

Nested within the class of recursive languages are the context-sensitive languages. A context-sensitive language is one where the size of the $\text{TM}$'s tape needed to decide the language is bounded. The languages $\{a^nb^nc^n\}$ and $\{n_a(w)=n_b(w)=n_c(w)\}$ are both context sensitive. In both cases, the amount of tape used is equal to the size of the input string, plus cells for a blank at each end of the string. A $\text{TM}$ that only uses its tape up to a constant factor times the input size is called a linear bounded automaton (LBA). The following table summarizes what we have explained so far about recursively enumerable languages. Each language class is a superset of the one below it.

Language Class	Grammar	Machine
Recursively enumerable	Type 0 (Unrestricted)	$\text{TM}$ Recognizer
Recursive	Type 0 (Unrestricted)	$\text{TM}$ Decider
Context-sensitive	Type 1 (Non-contracting)	LBA

Properties of recursively enumerable languages

Now we’ll explore key attributes of recursively enumerable languages to complete our perspective of formal languages.

First, recursive languages are closed under complement. This comes directly from the fact that if a language, $L$, is recursive, then there is a machine, $M$, that decides it. To decide its complement, $\overline{L}$, all we need to do is to invert the output results, as illustrated in the machine $M'$ below.