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 ${\displaystyle L^{*}}$
• A concatenação ${\displaystyle L\circ P}$
• A união ${\displaystyle L\cup P}$
• A interseção ${\displaystyle 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.

Teoria da computação

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

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

Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e