Linguagem recursivamente enumerável: diferenças entre revisões
Tradução livre da página em inglês incentivado pelo professor Ruy de Queiroz |
|||
Linha 1: | Linha 1: | ||
{{esboço}} |
{{esboço}} |
||
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. |
|||
Uma [[linguagem formal]] é dita '''recursivamente enumerável''' se ela é computável, ou seja, se existe um [[algoritmo]] que reconhece esta linguagem mas que não necessariamente para qualquer entrada. Uma linguagem é computável quando existe uma [[máquina de Turing]] que sempre pára, com "sim" ou "1" para instâncias positivas. Para cadeias fora da linguagem a máquina de Turing pode não parar, contrariamente ao que acontece com as [[linguagem recursiva|linguagens recursivas]]. |
|||
O décimo [[Problemas de Hilbert|problema]] de [[Hilbert]] abrange a classe das linguagens recursivamente enumeráveis. |
O décimo [[Problemas de Hilbert|problema]] de [[Hilbert]] abrange a classe das linguagens recursivamente enumeráveis. |
||
== Definições == |
|||
Toda [[linguagem recursiva]] é também recursivamente enumerável. |
|||
Existem três equivalentes definições importantes para o conceito de uma linguagem recursivamente enumerável: |
|||
# Uma linguagem recursivamente enumerável formal é um [[subconjunto]] recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem. |
|||
# 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. |
|||
# 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. |
|||
== Propriedades de fecho == |
|||
As linguagens recursivamente enumeráveis são [[fecho|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]] <math>L^*</math> |
|||
* A [[concatenação]] <math>L \circ P</math> |
|||
* A [[União (matemática) | união]] <math>L \cup P</math> |
|||
* A [[interseção]] <math>L \cap P</math> |
|||
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. |
|||
== Links externos == |
|||
* [http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf Lecture slides] |
|||
== Referências == |
|||
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co. |
|||
* Kozen, D.C. (1997), ''Automata and Computability'', Springer. |
|||
{{Teoria da computação}} |
{{Teoria da computação}} |
Revisão das 04h39min de 7 de dezembro de 2011
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:
- Uma linguagem recursivamente enumerável formal é um subconjunto recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem.
- 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.
- 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.
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
- A concatenação
- A união
- A interseção
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.
Links externos
Referências
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- Kozen, D.C. (1997), Automata and Computability, Springer.