Linguagem recursivamente enumerável: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Tradução livre da página em inglês incentivado pelo professor Ruy de Queiroz |
|||
Linha 1:
{{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.
O décimo [[Problemas de Hilbert|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 [[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}}
| |||