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