Lista 3 Teoria Da Computa O Respondida

1065 palavras 5 páginas
UNIVERSIDADE FEDERAL DA PARAÍBA
Centro de Ciências Aplicadas e Educação
Campus IV do Litoral Norte
Rio Tinto e Mamanguape

Disciplina: Teoria da Computação (2014-1)
Professor: Joelson Nogueira de Carvalho

Lista de Exercícios – Unidade III

Aluno: Matrícula:

1. Apresente a Hierarquia de Chomsky e indique sua finalidade.
Hierarquia de Chomsky tem como principal mérito agrupar as linguagens em classes, de tal forma que elas possam ser hierarquizadas de acordo com a sua complexidade relativa. Como resultado, é possível antecipar as propriedades fundamentais exibidas por uma determinada linguagem, ou mesmo vislumbrar os modelos de implementação mais adequados à sua realização, conforme a classe a que pertença.
Assim, o interesse prático pela Hierarquia de Chomsky se deve especialmente ao fato de ela viabilizar a escolha da forma mais econômica para a realização dos reconhecedores das linguagens, de acordo com a classe a que elas pertençam nessa hierarquia, evitando-se, portanto, o uso de formalismos mais complexos que o necessário, e o emprego de reconhecedores desnecessariamente ineficientes para as linguagens de menor complexidade.
2. O que é uma linguagem “decidível”? E uma “linguagem aceita”?
Dizemos que umalinguagem L é MT-decidível (ouqueuma MT decide L) se existeumaMáquina de Turing tal que, dada qualquer cadeia, pára com resposta SIM, se acadeia é umasentença de L, ou com a resposta NÃO, se a cadeianão é umasentença de L.
Dizemosqueumalinguagem L é MT-aceita

Relacionados

  • Teorias da vinculação
    1751 palavras | 8 páginas
  • Teoria da decisão
    3098 palavras | 13 páginas
  • A história da ciência - bbc (2 e 3) + teorias da criação e datação de fósseis.
    2127 palavras | 9 páginas
  • 3 Lista Estatistica Indutiva Correla o
    1390 palavras | 6 páginas
  • Teoria da comuinicação
    5834 palavras | 24 páginas
  • Teoria da refrigeração
    4332 palavras | 18 páginas
  • UNIDADE 2 ASPECTOS TEORICOS DA COMPUTA O
    1419 palavras | 6 páginas
  • Teorias da depressão
    1939 palavras | 8 páginas