Aspectos Teoricos

Prévia do material em texto

Aspectos Teoricos – Estudos Disciplinares 
T2826E-4 – Diogo Alexandro Silva Oliveira 
 
Modulo I 
Ex- 1 
 
Justificativa: Hierarquia de Chomsky: a componente regular, a livre de contexto e a 
dependente de contexto. A Linguagem Natural (Português, Italiano, Inglês, etc) é um exemplo 
de Linguagem Irrestrita. 
Ex2- 
 
Justificativa: A análise de cada palavra de um programa escrito em uma Linguagem de 
Programação qualquer, denominada Análise Léxica, usa os algoritmos obtidos do estudo das 
Linguagens Regulares. Estes algoritmos são a realização do modelo computacional 
denominado Máquina de Estados Finitos 
 
 
 
 
Ex3- 
 
Justificativa: As linguagens regulares são geradas pelas gramáticas regulares e são 
reconhecidas pelos autômatos finitos sem a presença de uma memoria auxiliar. 
Modulo III 
Ex1- 
 
Justificativa: Os autômatos com pilha compreendem a classe das linguagens livres de contexto, 
de acordo com a Hierarquia de Chomsky e, portanto, são modelos de computação 
equivalentes às gramáticas livres de contexto. Um autômato finito com acesso a 
uma pilhas não possui capacidade de computação equivalente ao de uma máquina de Turing. 
 
 
 
 
 
 
 
 
Ex2- 
 
Justificativa: A máquina de Turing não tem o seu poder computacional ampliado através de 
qualquer alteração estrutural 
Ex4- 
 
Justificativa: Qualquer programa de computador pode ser traduzido em uma máquina de 
Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de 
programação de propósito geral; assim, a tese é equivalente a dizer que qualquer linguagem 
de programação de propósito geral é suficiente para expressar qualquer algoritmo.