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