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

editar

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

editar

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:

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

editar
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

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

Ligações externas

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