ASPECTOS TEORICOS DA COMPUTAÇÃO

ASPECTOS TEORICOS DA COMPUTACÃO

1) A Hierarquia de Chomsky prevê quatro tipos de Linguagens, que são denominadas respectivamente:

Resposta: C: Regular, Livre de Contexto, Dependente de Contexto e Irrestrita;

Justificativa: Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica.

2) Assinale a alternativa que apresenta uma máquina conceitual capaz de reconhecer apenas a componente regular das Linguagens previstas na Hierarquia de Chomsky.

Resposta: C: Máquina de Estados Finitos;

Justificativa: Uma máquina de estados finitos (FSM - do inglês Finite State Machine) ou autômato finito é um modelo matemático usado para representar programas de computadores ou circuitos lógicos. O conceito é concebido como uma máquina abstrata que deve estar em um de seus finitos estados. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.

3) Assinale a alternativa que apresenta um elemento que não diz respeito à máquina de estados finitos:

Resposta: D: Memória auxiliar;

Justificativa: Um estado descreve um nó de comportamento do sistema em que está à espera de uma condição para executar uma transição. Normalmente, um estado é introduzido quando o sistema não reage da mesma forma para uma mesma condição. No exemplo de um sistema de rádio de carro, quando se está ouvindo uma estação de rádio, o estímulo "próximo" significa ir para a próxima estação. Mas quando o sistema está no estado de CD, o estímulo "próximo" significa ir para a próxima faixa. O mesmo estímulo desencadeia ações diferentes, dependendo do estado atual. Em algumas representações de estado finito máquina, também é possível associar ações a um estado:

Ação de entrada: o que é realizado ao entrar no estado,

Ação de 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?

Resposta: A: Regular, Regular, Livre de Contexto, respectivamente;

Justificativa: L1 e L2 são regulares pois pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular. 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 à forma geral

5) As Linguagens Dependentes de Contexto:

Resposta: B: podem ser reconhecidas por uma máquina de Turing;

Justificativa: A máquina de Turing é um autómato, com uma unidade de controlo e com um dispositivo especial que funciona simultaneamente como entrada (onde lê), armazenamento, e saída (onde escreve). Esse dispositivo é uma fita unidimensional que contém um número ilimitado de células cada uma das quais pode conter um único símbolo. Essa é a sua característica distintiva em relação aos autómatos finitos (que não têm dispositivo de armazenamento) e aos autómatos de pilha (que armazenam numa pilha ).

6) " 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.

Resposta: E: Linguagens Irrestritamente Enumeráveis

Justificativa: Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras:

Eles podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada;

Eles podem manipular a pilha ao efetuar uma transição.