Logo Passei Direto

A maior rede de estudos do Brasil

Grátis
5 pág.
ASPECTOS TEÓRICOS DA COMPUTAÇÃO - MÓDULO 1

Pré-visualização | Página 1 de 1

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;
Justificativa:
Em uma Linguagem de Programação ocorrem três componentes da Hierarquia de Chomsky: a componente regular, a livre de contexto e a depende de contexto.
A Linguagem Natural (Português, Italiano, etc.) é um exemplo de Linguagem Irrestrita.
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 Earl finita;
e) Máquina de Turing com fita finita;
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”.
3- Assinale a alternativa que apresenta um elemento que não diz respeito a autômatos finitos:
a) Unidade de controle;
b) Cursor;
c) Fita de entrada;
d) Memória auxiliar;
e) Movimento do “cabeçote” (cursor) de leitura sempre à direita.
Justificativa:
Um estado descreve um nó de comportamento do sistema em que está à espera de uma condição para executar uma transição. O mesmo estímulo desencadeia ações diferentes, dependendo do estado atual.
Ação de entrada: o que é realizado ao entrar no estado.
Ação e saída: o que é executado ao sair do estado.
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 regulares;
Justificativa:
L1 e L2 são regulares pois pode-se criar uma nova classe de gramáticas de grande importância por possuírem propriedades adequadas para a obtenção de reconhecedores simples. L3 é livre de contexto pois é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções de forma geral.
5- As Linguagens Dependentes de Contexto:
a) São reconhecidas por autômatos de pilha;
b) Podem ser reconhecidas por uma máquina da 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;
Justificativa:
As Linguagens Dependentes de Contexto e as Linguagens Recursivamente Enumeráveis são geradas pelas gramáticas sensíveis a contexto e irrestritas, respectivamente e são possíveis de serem processadas pela Máquina conceitual denominada Máquina de Turing.
6- Assinale a alternativa 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=abc, 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;
Justificativa:
A linguagem dependente de contexto é passível de ser processada pela 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 = anbncm, n>0, m>0}
b) L = {w | w = anbncndm, n>0, m>0}
c) L = {w | w = anbmcndl, n>0, m>0, l>0}
d) L = {w | w = anbncmdm, n>0, m>0}
e) L = {w | w = anbmcmdn, n>0, m>0}
Justificativa:
Tem-se que L = {w | w = anbncndm, n>0, m>0} é dependente de contexto, pois existe um vínculo de número de ocorrências entre três símbolos, a saber: “a”, “b”, “c”. Esta Linguagem não pode ser aceita por um autômato de pilha.
8- "O estudo sistemático das linguagens formais teve um forte impulso no final da década de 1950, quando o linguista 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 evoluí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
Justificativa:
Ocorrem três componentes da Hierarquia de Chomsky: a regular, livre de contexto e a dependente de contexto + a linguagem irrestrita.