Linguagem recursivamente enumerável: diferenças entre revisões
m A migrar 14 interwikis, agora providenciados por Wikidata em d:q1073063 |
Fusão com Linguagens recursivamente enumeráveis. |
||
Linha 1: | Linha 1: | ||
⚫ | |||
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. |
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 [[Problemas de Hilbert|problema |
O décimo [[Problemas de Hilbert|problema de Hilbert]] abrange a classe das linguagens recursivamente enumeráveis. |
||
{{TOC}} |
|||
== Definições == |
== Definições == |
||
Linha 14: | Linha 12: | ||
[[Linguagem regular]], [[linguagem livre de contexto]] e linguagem recursiva são todas recursivamente enumeráveis. |
[[Linguagem regular]], [[linguagem livre de contexto]] e linguagem recursiva são todas recursivamente enumeráveis. |
||
O [[teorema de Post]] mostra que '''[[RE (complexidade)|RE]]''', juntamente com seu [[complemento (complexity)|complemento]] [[co-RE]], correspondem ao primeiro nível da [[hierarquia aritmética]]. |
|||
== Propriedades de fecho == |
== Propriedades de fecho == |
||
Linha 24: | Linha 24: | ||
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. |
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 == |
== Referências == |
||
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co. |
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co. |
||
* Kozen, D.C. (1997), ''Automata and Computability'', Springer. |
* Kozen, D.C. (1997), ''Automata and Computability'', Springer. |
||
== Ligações externas == |
|||
⚫ | |||
{{Teoria da computação}} |
{{Teoria da computação}} |
||
⚫ | |||
[[Categoria:Teoria da computação]] |
[[Categoria:Teoria da computação]] |
Revisão das 16h22min de 2 de junho de 2013
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.
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
- 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.
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