Aspectos Teóricos da Computação

Prévia do material em texto

Aspectos Teóricos da Computação
Módulo 1 – Questão 1 
Justificativa: A 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.
Módulo 2 – Questão 2
Justificativa: Uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível. Também é conhecida como tipo-0 na hierarquia de Chomsky das linguagens formais.
Módulo 3 – Questão 5
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.
Módulo Complementar I – Questão 3
O enunciado que se segue é extraído da prova ENADE 2005. Trata-se de uma questão muito interessante, pois permite ao leitor identificar duas classes previstas na Hierarquia de Chomsky, a saber: a classe das Linguagens Regulares e a classe das Linguagens Livres de Contexto. O leitor também pode observar que o estudo de Linguagens Formais e Autômatos tem aplicação imediata no projeto e implementação de processadores de Linguagens de Programação, ou seja, Compiladores. Cumpre observar que expressões matemáticas constituem uma das estruturas sintáticas encontradas em Linguagens de Programação. Prossiga com a leitura do enunciado e assinale a alternativa correta. ENADE 2005 - Questão 64 - Considere a necessidade de se implementar um componente de software que realiza cálculos de expressões matemáticas simples para as operações básicas (soma, subtração, multiplicação, divisão e exponenciação). O software reproduz na tela do computador a entrada, os resultados parciais e o resultado final da expressão e, ainda, trata os operadores de exponenciação, multiplicação e divisão com precedência sobre os operadores de soma e subtração. Para obter o referido software, é correto que o projetista
I defina uma cadeia de caracteres para armazenar e imprimir toda a expressão de entrada.
II defina uma gramática regular para identificar as expressões aritméticas válidas.
III defina um reconhecedor de linguagem regular com autômato finito determinístico.
IV especifique a ordem de precedência dos operadores com uma notação de gramática livre de contexto.
Estão certos apenas os itens:
Justificativa: A única afirmação incorreta é a II. Tal identificação é realizada por uma gramática livre de contexto, que também seria responsável por especificar a ordem de precedência dos operadores. A gramática regular deve ser utilizada para identificar os tokens da expressão aritmética.
Módulo Complementar I – Questão 5
Justificativa: Gramática irrestrita (conhecida também como Gramática com estrutura de frase) é também conhecida como Tipo 0 da Hierarquia de Chomsky, que são aquelas às quais nenhuma limitação é imposta. São capazes de gerar linguagens recursivamente enumeráveis.
Módulo Complementar II – Questão 1 
Justificativa: O conjunto de todos os números inteiros é um conjunto infinito enumerável. O conjunto de todos os números reais é um conjunto infinito não-enumerável.