Recursively Enumerable Language

In mathematics, logic, and computer science, a recursively enumerable language is a type of formal language, also known as partially decidable, or Turing-recognizable. In the Chomsky hierarchy it is known as a type-0 language. The class of all recursively enumerable languages is called RE.

A recursively enumerable language (also known as "partially decidable" or "semi-decidable") is an important concept in computational linguistics and the theory of formal languages. This term is tied to the field of computability and defines the class of languages that can be recognized by computing devices with unlimited resources. Let us take a closer look at what a recursively enumerable language is and how it relates to computational linguistics.

Definition of a recursively enumerable language

A recursively enumerable language is a language for which there exists a computing device (such as a Turing machine) that can enumerate (generate) all valid strings of the given language. However, this device may fail to halt for strings that do not belong to the language, in which case it will loop forever.

Thus, recursively enumerable languages have the property of "partial decidability", meaning that a program can be built that will answer "Yes" for every string belonging to the language, and, for strings that do not belong to the language, will possibly answer "No" or fail to halt.

Relation to computational linguistics

In computational linguistics, which studies natural language processing (NLP), understanding recursively enumerable languages is of fundamental importance. This is tied to several aspects:

1. Syntactic analysis: Recursively enumerable languages are used to determine the syntactic correctness of sentences and phrases in natural languages. A syntactic analyzer (parser) can work with grammars describing such languages in order to identify the structure of sentences.

2. Text generation: When building text generation systems, for example for the automatic generation of articles, scripts, or answers to questions, it is necessary to work with recursively enumerable languages. Text generation involves constructing correct sentences and texts that conform to given rules.

3. Processing unstructured data: Much data, such as the text of web pages, social media, and documents, can be unstructured and is analyzed using methods related to recursively enumerable languages.

Definitions

There are three main equivalent definitions of the concept of a recursively enumerable language.

1. A recursively enumerable formal language — is a recursively enumerable subset of the set of all possible words over the alphabet of the language.
2. A recursively enumerable language — is a formal language for which there exists a Turing machine (or other computable function) that enumerates all valid strings of the language. Note that if the language is infinite, an enumeration algorithm can be chosen that avoids repetitions, since for the string numbered n one can check whether it has «already» been output under a number smaller than n. If it has, then the output numbered n+1 is used instead (recursively), again checking whether it is «new».
3. A recursively enumerable language — is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept any input string from the language, but will either halt and reject, or never halt at all, for any input string not from the language. Recursive languages require the Turing machine to halt in every case.

All regular, context-free, context-sensitive, and recursive languages are recursively enumerable.

Post's theorem shows that RE together with its complement co-RE correspond to the first level of the arithmetical hierarchy.

Closure properties

Recursively enumerable languages are closed under the following operations. Let L and P — be two recursively enumerable languages, then the following languages are also recursively enumerable:

• the Kleene star of L
• the concatenation of L and P
• the union
• the intersection

Note that recursively enumerable languages are not closed under difference or complement. The set difference L\P may or may not be recursively enumerable. If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.

It is important to note that in computational linguistics, as in computability theory, there are many methods and algorithms for working with recursively enumerable languages, and they play an important role in building intelligent systems capable of processing and generating natural language.

Example

The set of halting Turing machines is recursively enumerable, but not recursive. Indeed, one can run the Turing machine and accept if the machine halts, hence it is recursively enumerable. On the other hand, the problem is undecidable.

Some other recursively enumerable languages that are not recursive include:

• The correspondence problem
• Mortality (computability theory)

• Entscheidungs problem (the decision problem)

• 

See also

• [[b8376]]
• Computably enumerable set
• Recursion

See also

• Recursive Language