# Recursively enumerable language

 related topics {math, number, function} {language, word, form}

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

## Contents

### Definitions

There exist three equivalent major definitions for the concept of a recursively enumerable language.

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. That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:

• the Kleene star L * of L
• the concatenation $L \circ P$ of L and P
• the union $L \cup P$
• the intersection $L \cap P$

Note that recursively enumerable languages are not closed under set difference or complementation. 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.