N2 LINGUAGENS FORMAIS E AUTÔMATOS

Prévia do material em texto

• Pergunta 1 
1 em 1 pontos 
 
Observe a figura a seguir, que apresenta um grafo ilustrativo do jogo Pac-
Man, em que cada aresta do grafo é composta por pontos que alimentam o 
personagem (Pac-Man) e propiciam que ele se locomova pelo grafo: 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. 
 
 
Fonte: Menezes (2015, p. 240). 
#PraCegoVer : na ilustração, é apresentado um grafo ilustrativo do jogo 
Pac-Man, em que cada aresta do grafo é composta por pontos que 
alimentam o personagem (Pac-Man) e propiciam que ele se locomova pelo 
grafo. Na figura, os símbolos representam o alimento do Pac-Man; já as 
setas representam os possíveis caminhos de movimentação no grafo, 
enquanto a ilustração do fantasma representa o adversário a ser 
contornado. 
 
Considerando a figura ilustrada, a fim de apresentar o esquema lógico do 
funcionamento dos grafos a partir da hierarquia de Chomsky, analise as 
afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) 
Falsa(s). 
 
I. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas de 
grafos, em geral, distinguem entre variáveis e terminais (todos os símbolos 
– no caso, grafos – são tratados como terminais). 
II. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas 
de grafos, em geral, possuem um grafo inicial. 
III. ( ) Comparativamente com as gramáticas de Chomsky, as gramáticas 
de grafos, em geral, apresentam a linguagem gerada como um conjunto de 
grafos que podem ser gerados, via derivações, a partir do grafo inicial. 
IV. ( ) As gramáticas de grafos não constituem um caso particular das 
gramáticas categoriais, e sim das gramáticas semânticas. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
Resposta Selecionada: 
F, V, V, F. 
Resposta Correta: 
F, V, V, F. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. A afirmativa II é 
verdadeira, pois, de fato, as gramáticas de grafos, em geral, 
apresentam a linguagem gerada como um conjunto de grafos 
que podem ter como origem as derivações, a partir do grafo 
 
inicial. A afirmativa III também é verdadeira, uma vez que as 
gramáticas de grafos, em geral, apresentam a linguagem gerada 
por definição como um conjunto de grafos que podem ser 
gerados, via derivações, a partir do grafo inicial. 
 
• Pergunta 2 
1 em 1 pontos 
 
A elaboração de um autômato com pilha, a partir de uma gramática livre do 
contexto, proporciona a produção de um reconhecedor para uma 
linguagem livre do contexto, a partir de sua gramática básica e instantânea. 
Assim, a partir das linguagens livres de contexto, é possível entender um 
universo extenso de linguagens. 
 
Assinale a alternativa que indica como qualquer linguagem livre de 
contexto pode ser identificada. 
 
Resposta 
Selecionada: 
 
Trata-se de um autômato com estrutura de dados em pilha, 
apresentando apenas um estado de controle lógico. 
Resposta 
Correta: 
 
Trata-se de um autômato com estrutura de dados em pilha, 
apresentando apenas um estado de controle lógico. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, a definição que se 
emprega para exemplificar uma linguagem livre de contexto 
parte de um autômato com estrutura de dados em pilha, 
apresentando apenas um estado de controle lógico, o que 
implica, por sua vez, que a estrutura de pilha se torne suficiente 
para a utilização de uma única memória. 
 
 
• Pergunta 3 
0 em 1 pontos 
 
A análise sintática é responsável pelas propriedades livres das linguagens 
como, por exemplo, a verificação gramatical dos programas. Já a análise 
semântica procura dar uma interpretação para a linguagem como, por 
exemplo, um significado ou valor para um determinado programa. 
 
Considerando o parágrafo acima, analise as afirmativas a seguir e assinale 
V 
para a(s) verdadeira(s) e F para a(s) falsa(s) sobre as abordagens das 
linguagens formais. 
 
 
I. ( ) No tipo operacional, tem-se que um autômato ou uma máquina 
abstrata é baseada em funções, em instruções primitivas e na 
especificação de como cada instrução modifica cada estado. 
II. ( ) No tipo axiomático, temos a associação de regras para a busca aos 
componentes da linguagem. 
III. ( ) No tipo denotacional, temos um domínio que permite a 
caracterização do conjunto de componentes que são admissíveis na 
linguagem, assim como os valores dos subcomponentes. 
IV. ( ) No tipo operacional e no tipo de notacional, as regras são usadas 
para permitir afirmar o que é verdadeiro e o que é falso, após a ocorrência 
das regras para a busca aos componentes de uma linguagem. 
 
Assinale a alternativa que apresenta a sequência correta: 
Resposta Selecionada: 
V, F, V, V. 
Resposta Correta: 
F, V, F, F. 
Comentário 
da resposta: 
Sua resposta está incorreta. A sequência está incorreta, pois a 
afirmativa I é falsa, porque, no tipo operacional, tem-se que um 
autômato ou uma máquina abstrata é baseada em estados, em 
instruções primitivas e na especificação de como cada instrução 
modifica cada estado. A afirmativa III também é falsa porque, no 
tipo denotacional, temos um domínio que permite a 
caracterização do conjunto de palavras que são admissíveis na 
linguagem, logo, temos uma construção específica de valores e 
de subcomponentes. E, por fim, a afirmativa IV também é falsa, 
porque, apenas no tipo denotacional, as regras são usadas para 
permitir afirmar o que é verdadeiro e o que é falso, após a 
ocorrência de cada regra. 
 
 
• Pergunta 4 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“Podemos, então, definir que um alfabeto é um conjunto finito de símbolos 
ou de caracteres. Por sua vez, a palavra ou a cadeia de caracteres, ou a 
sentença, é uma sequência de característica finita de símbolos do alfabeto 
da linguagem que, reunidos, formam um significado”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 103. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta 
entre elas. 
 
 
I. Em uma linguagem formal, o conjunto finito de todas as palavras forma a 
gramática da linguagem. 
Pois: 
II. A gramática é a definição de regras que, quando aplicadas, tais 
diretrizes geram as palavras a partir das expressões. Assim, um conjunto 
de todas as palavras geradas por uma gramática dá origem a uma 
linguagem formal. 
 
A seguir, assinale a alternativa correta. 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, e a II é uma 
justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, e a II é uma 
justificativa correta da I. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a asserção I é 
uma proposição verdadeira. O conjunto finito de todas as 
palavras, em uma linguagem formal, é o que dá origem a uma 
gramática, por definição. A asserção II também é uma 
proposição verdadeira e justifica a I, porque a gramática, nada 
mais é, do que a representação das definições das regras que 
vão compor a linguagem. Quando essas regras são aplicadas, 
definem as palavras com base nas expressões; logo, um 
conjunto de todas as palavras da gramática dá origem a uma 
linguagem formal. 
 
 
• Pergunta 5 
0 em 1 pontos 
 
As pilhas são estruturas de dados do tipo LIFO ( last in, first out ), que 
podem ser empregadas em autômatos, onde basicamente temos a 
estruturação na qual o último elemento a ser inserido será o primeiro a ser 
retirado. Assim, uma pilha permite acesso a apenas um item de dados, isto 
é, ao último inserido. Para processar o penúltimo item inserido, deve-se 
remover o último. 
 
Considerando o texto apresentado e a estruturação lógica de um autômato 
com pilha, analise as afirmativas a seguir e assinale V 
para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. ( ) O autômato com pilha é similar ao autômato finito, porém, no 
autômato com pilha, insere-se uma pilha como memória adicional.II. ( ) A pilha é inserida como um autômato da fita de entrada e não 
apresenta limite máximo de tamanho, podendo ser aumentada até onde se 
desejar. 
 
III. ( ) No autômato com pilha, o último ícone memorizado é o último a ser 
lido 
IV. ( ) A base de uma pilha é firme e define o seu início. O topo é variável 
e define a posição do último ícone memorizado. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Sua resposta está incorreta. A sequência está incorreta, pois, no 
autômato com pilha, o último ícone memorizado é o primeiro a 
ser lido, e não o último a ser lido, essa é a definição de 
funcionamento de qualquer tipo de estrutura de dados em 
pilha, logo, podemos afirmar que a afirmativa III é falsa. A 
afirmativa I é verdadeira, porque o autômato com pilha é 
semelhante, na sua estrutura, ao autômato finito, dadas as suas 
características, porém, no autômato com pilha, emprega-se uma 
pilha como memória adicional; basicamente, essa é a diferença 
entre ambos. A afirmativa II está correta, pois a pilha é inserida 
como um autômato da fita de entrada e não apresenta limite 
máximo de tamanho, podendo ser aumentada até onde se 
desejar, logo, não existindo limite, cabe escalonar o tamanho 
até onde se desejar. A afirmativa IV também é verdadeira, 
porque a estrutura da pilha divide-se na base firme, que define 
seu início, e no topo, que varia e define a posição do último 
ícone memorizado, por definição de como funciona a estrutura 
de dados de uma pilha. 
 
 
• Pergunta 6 
1 em 1 pontos 
 
Leia o trecho a seguir: 
“O estudo da computabilidade tem como objetivo determinar a 
solucionabilidade de problemas, a partir da existência de algoritmos. 
Portanto, investiga os limites do que pode ser implementado em um 
computador, evitando a pesquisa de soluções inexistentes. A abordagem 
da compatibilidade é centrada nos problemas de decisão (do tipo sim/não)”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 103. 
 
A partir do apresentado, analise as asserções a seguir e a relação proposta 
entre elas. 
 
 
I. O estudo da computabilidade usa com frequência o princípio da redução. 
Pois: 
II. Ele analisa e determina as soluções de problemas a partir de algoritmos 
computacionais. 
 
A seguir, assinale a alternativa correta. 
 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, mas a II não 
é uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, mas a II não 
é uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, a asserção I é uma 
proposição verdadeira, já que, de fato, o estudo da 
computabilidade é usado com frequência para o princípio da 
redução, pois investiga a solucionabilidade de um problema a 
partir de outro. A asserção II não é uma justificativa correta da I, 
uma vez que a justificativa de analisar soluções de problemas 
não se relaciona ao estudo da computabilidade aplicada ao 
princípio da redução, logo, são independentes. 
 
 
• Pergunta 7 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“A classificação das gramáticas, segundo a hierarquia de Chomsky, 
começa pelo tipo 0, com maior nível de liberdade em suas regras, e 
aumenta as restrições até o tipo 3. Cada nível é um super conjunto do 
próximo. Logo, uma gramática de tipo n é, consequentemente, uma 
linguagem de tipo n - 1”. 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas 
universais e computabilidade. Porto Alegre: Grupo A, 2011. p. 121. 
 
Sobre os níveis de aplicabilidade da hierarquia de Chomsky, analise as 
afirmativas a seguir. 
 
I. Na classificação da hierarquia de Chomsky, o tipo 0 se refere às 
gramáticas com estrutura de fase, que apresentam maior nível de liberdade 
nas suas regras. 
II. Na classificação da hierarquia de Chomsky, o tipo 2 se refere às 
gramáticas livres de contexto, que são empregadas na análise sintática da 
teoria da computação. 
 
III. Na classificação da hierarquia de Chomsky, o tipo 3 se refere às 
gramáticas regulares, que são empregadas na análise léxica da teoria da 
computação. 
IV. Na classificação da hierarquia de Chomsky, o tipo 1 se refere às 
gramáticas sensíveis à semântica, que são empregadas nas linguagens de 
programação. 
 
Está correto o que se afirma em: 
Resposta Selecionada: 
I, II e III, apenas. 
Resposta Correta: 
I, II e III, apenas. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, porque, na 
hierarquia de Chomsky, o tipo 0 se refere às gramáticas com 
estrutura de fase ou recursivamente enumeráveis que, por sua 
vez, apresentam maior nível de liberdade. Quanto às 
classificações, o tipo 2 se refere às gramáticas livres de contexto 
e o tipo 3 remete às gramáticas regulares. O tipo 2 é empregado 
na análise sintática, enquanto o tipo 3 é empregado na análise 
léxica. 
 
 
• Pergunta 8 
1 em 1 pontos 
 
Leia o trecho a seguir: 
“A unidade de controle apresenta um número finito e predefinido de 
estados. A cabeça da fita tem a finalidade de ler o símbolo de uma célula, 
uma a cada vez, e gravar um novo símbolo por vez. Após a 
leitura/gravação (a gravação é realizada na mesma célula de leitura), a 
cabeça vai mover uma célula para a direita ou para a esquerda”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 215. 
 
A partir do apresentado, analise as asserções a seguir e a relação proposta 
entre elas. 
 
I. A fita é usada simultaneamente como dispositivo de entrada, de saída e 
de memória de trabalho. 
Pois: 
II. Define o estado da máquina e comanda as leituras, as gravações e o 
sentido de movimento da cabeça. 
 
A seguir, assinale a alternativa correta 
 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, mas a II não 
é uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, mas a II não 
é uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a asserção I é 
verdadeira, já a fita é finita à esquerda e infinita à direita e é tão 
grande quanto necessário, sendo dividida em células, cada uma 
armazenando um símbolo, logo, as asserções I e II, são 
verdadeiras, mas a II não é razão ou justificativa da I. 
 
 
• Pergunta 9 
0 em 1 pontos 
 
Leia o trecho a seguir: 
“As linguagens livres de contexto são bastante utilizadas na conceituação 
de gramáticas, empregadas nas linguagens de programação, que por sua 
vez, podem derivar vários tipos de aplicações com o uso dos autômatos e 
dos formalismos presentes nas linguagens”. 
 
DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação : máquinas 
universais e computabilidade. 3. ed. Porto Alegre: Grupo A, 2011. v. 5, p. 
114. 
 
Considerando o excerto apresentado, sobre as propriedades das 
gramáticas livres de contexto, analise as afirmativas a seguir: 
 
I. As linguagens livres do contexto ou tipo 2 são desenvolvidas a partir das 
gramáticas livres do contexto. 
II. Em aplicações como compiladores, é comum a caracterização da 
derivação das palavras em gramáticas livres do contexto. 
III. Como definição, temos, para uma estipulada gramática livre do 
contexto, a simbolização da derivação de palavras na forma de grafos. 
IV. Uma gramática livre do contexto é uma gramática na qual o lado 
esquerdo das criações inclui exatamente uma variável. 
 
Está correto o que se afirma em: 
 
Resposta Selecionada: 
I, II e IV, apenas. 
 
 
Resposta Correta: 
 
I e IV, apenas. 
Comentário 
da resposta: 
Sua resposta está incorreta. A alternativa está incorreta, pois 
houve uma inversão dos conceitos apresentados: em aplicações 
como compiladores, é comum a caracterização da derivação das 
palavras em estrutura de dados de árvore, partindo daraiz até 
as folhas, e não a caracterização da derivação das palavras em 
gramáticas livres do contexto. Como definição, temos, para uma 
estipulada gramática livre do contexto, a simbolização da 
derivação de palavras na forma de árvores, e não de grafos. 
 
• Pergunta 10 
1 em 1 pontos 
 
Leia o texto a seguir: 
“Sintaticamente falando, não existe uma noção de programa ‘errado’: neste 
caso, simplesmente não é um programa da linguagem em questão. Por 
outro lado, um programa sintaticamente válido (‘correto’) pode não ser o 
programa que o programador esperava escrever. Assim, a questão de 
considerar um programa ‘correto’ ou ‘errado’ deve considerar se o mesmo 
modela adequadamente o comportamento desejado”. 
 
MENEZES, P. B. Linguagens formais e autômatos . Porto Alegre: 
UFRGS; Grupo A, 2011. 3 v. p. 17. 
 
Considerando o texto apresentado, assinale a alternativa correta sobre 
análise sintática e análise léxica. 
 
Resposta 
Selecionada: 
 
A análise sintática vê a análise léxica como um tipo especial, e 
podemos dizer que é centrada nos componentes 
considerados básicos da linguagem. 
Resposta 
Correta: 
 
A análise sintática vê a análise léxica como um tipo especial, e 
podemos dizer que é centrada nos componentes 
considerados básicos da linguagem. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a análise 
sintática vê a análise léxica como um tipo especial, e podemos 
dizer que é centrada nos componentes considerados básicos da 
linguagem. Isso porque os limites entre a sintaxe e a semântica 
nem sempre são claros. Já a ocorrência de um nome em um 
programa pode ser tratada de forma igualmente fácil com um 
problema sintático ou semântico, assim, as linguagens formais 
também se preocupam com os problemas léxicos.