Linguagem recursivamente enumerável

Em matemática, lógica e ciência da computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível. Também é conhecida como tipo-0 na hierarquia de Chomsky das linguagens formais.

O décimo problema de Hilbert abrange a classe das linguagens recursivamente enumeráveis.

Definições

Existem três equivalentes definições importantes para o conceito de uma linguagem recursivamente enumerável:

1. Uma linguagem recursivamente enumerável formal é um subconjunto recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem.
2. Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá enumerar todas as cadeias válidas da linguagem. Note que, se a linguagem é infinita, o algoritmo de enumeração fornecido pode ser escolhido de forma que evite repetições, uma vez que podemos testar se a cadeia produzida para o número n é já é produzida para um número que é inferior a n. Se ela já é produzida, use a saída da entrada n+1 (recursivamente), mas mais uma vez, teste se é uma cadeia nova.
3. Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá parar e aceitar quando se roda com qualquer cadeia da linguagem na entrada e pode parar e rejeitar ou entrar em loop quando se roda com qualquer cadeia que não é da linguagem. Esta é a diferença entre linguagem recursiva, que exige que a máquina de Turing sempre pare.

Linguagem regular, linguagem livre de contexto e linguagem recursiva são todas recursivamente enumeráveis.

O teorema de Post mostra que RE, juntamente com seu complemento co-RE, correspondem ao primeiro nível da hierarquia aritmética.

Propriedades de fecho

As linguagens recursivamente enumeráveis são fechadas sob as seguintes operações. Isto é, se L e P são duas linguagens recursivamente enumeráveis, então as seguintes linguagens são também recursivamente enumeráveis:

• O Fecho de Kleene $L^{*}$
• A concatenação $L\circ P$
• A união $L\cup P$
• A interseção $L\cap P$

Note que as linguagens recursivamente enumeráveis não são fechadas sob diferença e complemento. A diferença L-P pode ou não ser recursivamente enumerável. Se L é recursivamente enumerável, então o complemento de L é recursivamente enumerável se e somente se L também for recursiva.

Referências

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springer.

Ligações externas

• Lecture slides