Linguagem tipo 0

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (719 palavras )
  • Download(s) : 0
  • Publicado : 10 de junho de 2012
Ler documento completo
Amostra do texto
O que é 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 daslinguagens formais.
Existem três equivalentes definições importantes para o conceito de uma linguagem recursivamente enumerável:
1. Uma linguagem recursivamente enumerável formal é um subconjuntorecursivamente 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 queirá 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 podemostestar 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 cadeianova.
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 epode 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.
Máquinade Turing:
• Se a máquina pára para toda palavra da linguagem sobre o alfabeto de entrada, ela é reconhecida pela Máquina de Turing.
• Uma linguagem aceita por uma Máquina de Turing é ditaenumerável recursivamente.
• Enumerável deriva do fato de que as palavras de qualquer linguagem enumerável recursivamente podem ser enumeradas ou listadas por uma Máquina de Turing.
Linguagens Recursivas:São compostas pelas linguagens para as quais existe pelo menos uma Máquina de Turing que pára para qualquer entrada, aceitando ou rejeitando.
Podemos afirmar que a classe das Linguagens...
tracking img