Aspectos Teóricos da Computação

Prévia do material em texto

ASPECTOS TEÓRICOS DA COMPUTAÇÃO – MÓDULO 1 – PROF SAMUEL
1 – A Hierarquia de Chomsky prevê quatro tipos de Linguagens, que são denominadas respectivamente:
A – Regular, Irregular, Contextual e Natural
B – Regular, Livre de Contexto, Dependente de Contexto e Natural
C – Regular, Livre de Contexto, Dependente de Contexto e Irrestrita
D – Regular, Irregular, Dependente de Contexto e Livre de Contexto
E – Regular, Irregular, Livre de Contexto e Natural
2 – Assinale a alternativa que apresenta uma máquina conceitual capaz de reconhecer apenas a componente regular das Linguagens previstas na Hierarquia de Chomsky.
A – Máquina de Estados Finitos
B – Autômato de Pilha
C – Máquina de Post
D – Máquina de Early finita
E – Máquina de Turing com fita finita
3 – Assinale a alterantiva que apresenta um elemento que não diz respeito a autômatos finitos:
A – Unidade controle
B – Cursor
C – Fita de entrada
D – Memória Auxiliar
E – Movimento do “cabeçote” (cursor) de leitura sempre à direita
4 - “As técnicas de construção de compiladores podem ser e são aplicadas fora da construção de compiladores em seu sentido mais estrito. Exemplo de sistemas de conversão
de arquivos que obtiveram considerável proveito de técnicas de construção de compiladores são os interpretadores PostScript, que convertem texto PostScript em instruções para
uma impressora específica.” (Grune et al. ). Dois módulos funcionais importantes de um compilador são o Analisador Léxico e o Analisador Sintático. A especificação, bem como os
algoritmos empregados em tais módulos estão associados ao estudo das classes das Linguagens Regulares e Livres de Contexto, respectivamente, ambas previstas na Hierarquia de
Chomsky.
Considere as seguintes linguagens definidas sobre o alfabeto S = {a, b, c}
L1 (w) = {w | w = a*b+ (a|b)n c | n > 0 }
L2(w) = {w | w = ambn (a|b)k c| m, n, k > 0 }
L3(w) = {w | w = anbm (a|b)n c| m > 1, n > 0}
Como L1, L2 e L3, são classificadas, em sentido estrito?
A – Regular, Regular, Livre de Contexto, respectivamente
B – Livre de Contexto, Livre de Contexto, Regular, respectivamente
C – Livre de Contexto, Regular, Dependente de Contexto, respectivamente
D – Regular, Livre de Contexto e Dependente de Contexto, respectivamente
E – Todas são Regulares5 – As linguaguens Dependentes de Contexto:
A – São reconhecidas por autômatos de pilha
B – Podem ser reconhecidas por uma máquina de Turing
C – São geradas por gramáticas livre de contexto
D – Não são consideradas como Linguagens Formais
E – São reconhecidas por uma Máquina de Turing com fita limitada
6 – Assinale a alterantiva INCORRETA:
A - A máquina de Turing para ser considerada como um modelo formal de procedimento efetivo, algoritmo ou função computável que deve descrever um algoritmo necessariamente
finito;
B - L = {w | w = an bn cn , n > 0} é uma linguagem dependente de contexto e portanto pode ser reconhecida por uma Máquina de Turing com fita limitada;
C - L = {w | w = an bn cm dm , n > 0, m > 0} é uma linguagem livre de contexto e portanto pode ser reconhecida por uma Máquina de Turing;
D - A máquina de Turing para ser considerada como um modelo formal de procedimento efetivo, algoritmo ou função computável que deve descrever um algoritmo cujos passos são
necessariamente executáveis mecanicamente em um tempo finito;
E - L = {w | w = an bn cn , n > 0} é uma linguagem dependente de contexto e portanto não pode ser reconhecida por uma Máquina de Turing ;
7 - Assinale a linguagem L definida sobre o alfabeto A = {a, b, c, d} que não pode ser reconhecida por um autômato com uma pilha:
A - L = {w | w = an bn cm , n > 0, m>0}
B - L = {w | w = an bn cn dm , n > 0, m> 0}
C - L = {w | w = an bm cn dl , n > 0, m> 0, l >0}
D - L = {w | w = an bn cm dm , n > 0, m > 0}
E - L = {w | w = an bm cm dn , n > 0, m > 0}
8 - " O estudo sistemático das linguagens formais teve um forte impulso no final da década de 1950, quando o lingüista Noam Chomsky publicou dois artigos apresentando o
resultado de suas pesquisas relativas à classificação hierárquica das linguagens. Até então, a teoria dos autômatos se apresentava razoavelmente eoluída, porém a das linguagens
formais ainda não se havia, de fato, estabelecido como disciplina... A classificação das linguagens formais, por ele (Chomsky) proposta, conhecida como 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..." (RAMOS, VEGA, NETO, cap.
2.6). Assinale a classe das Linguagens não prevista na hierarquia de Chomsky.
A – Linguagens Recursivamente Enumeráveis
B – Linguagens Sensíveis ao Contexto
C – Linguagens Livres de Contexto
D – Linguagens Regulares
E – Linguagens Adaptáveis