Atividade 2 UAM| Linguagens formais e automatos

Prévia do material em texto

 Pergunta 1 
1 em 1 pontos 
 
A teoria das linguagens formais foi desenvolvida com o intuito de aproximar 
as linguagens humanas, bem como a sua estruturação e formação, com as 
linguagens regulares e com o emprego dos autômatos, que têm, na sua 
base, as expressões e as gramáticas regulares. 
 
A partir do exposto, qual é a definição de expressões regulares? 
 
Resposta 
Selecionada: 
 
Um formalismo que expressa a construção de uma 
linguagem regular. 
Resposta Correta: 
Um formalismo que expressa a construção de uma 
linguagem regular. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a definição de 
expressões regulares visa a definir um formalismo denotacional, 
que pode ser considerado gerador, já que é provável inferir como 
construir, ou seja, gerar as palavras de uma linguagem regular. 
Dessa forma, uma expressão regular pode ser definida a partir de 
conjuntos básicos e operações de concatenação e de união, com o 
objetivo de construir uma linguagem regular. 
 
 
 Pergunta 2 
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 3 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“As gramáticas de grafos têm duas ideias fundamentais em suas estruturas. 
São elas: as regras de produção quanto aos pares de grafos, e a regra da 
derivação, que visa à substituição de um subgrafo de acordo com as regras 
 
de produção das linguagens, o que, por sua vez, orienta a estrutura da 
hierarquia de Chomsky, conforme o tipo de linguagem a ser gerada”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 169. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre 
elas. 
 
I. As gramáticas de grafos constituem um caso particular das gramáticas 
categóricas. 
Pois: 
II. A ideia básica consiste em substituir palavras por grafos de acordo com o 
conceito de gramática de Chomsky. 
 
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, já que as gramáticas de grafos são reflexos 
do caso particular da classificação de gramáticas categóricas. Essa é 
a definição proposta pela gramática de Chomsky. A asserção II 
também é uma proposição verdadeira e justifica a I, porque as 
gramáticas de grafos são um caso específico das gramáticas 
categóricas; logo, a elaboração delas consiste em substituir palavras 
por grafos, conforme o conceito de gramática de Chomsky. Dessa 
forma, a definição presente da gramática de Chomsky limita as 
categorias, criando o caso específico da gramática de grafos como 
uma situação singular das gramáticas categóricas. 
 
 
 Pergunta 4 
1 em 1 pontos 
 
As classes das linguagens regulares, livres do contexto, sensíveis ao 
contexto e recursivamente enumeráveis e suas inclusões próprias 
constituem a hierarquia de Chomsky. A criação de gramáticas regulares em 
grafos é uma das formas conhecidas de se generalizar o que conhecemos 
por gramáticas de Chomsky, que, por sua vez, têm demonstrado um imenso 
potencial para aplicações computacionais avançadas, como linguagens 
interpretativas de inteligência artificial. 
 
No que tange ao exposto, qual é a definição de hierarquia de Chomsky? 
 
Resposta 
Selecionada: 
 
Trata-se de uma classificação hierárquica das gramáticas 
formais com 4 níveis. 
Resposta Correta: 
Trata-se de uma classificação hierárquica das gramáticas 
formais com 4 níveis. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a definição da 
hierarquia de Chomsky se trata de uma classificação hierárquica 
das gramáticas formais com 4 níveis, sendo: tipo 0, tipo 1, tipo 2 e 
tipo 3, respectivamente; gramáticas com estrutura de fase; 
gramáticas sensíveis ao contexto; gramáticas livres de contexto e 
gramáticas regulares. 
 
 
 Pergunta 5 
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 defase 
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 6 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“As linguagens de programação são tratadas adequadamente na hierarquia 
de Chomsky. Existem linguagens que não são livres do contexto, para as 
quais o poder dos formalismos sensíveis ao contexto é excessivo, sendo 
inadequados, principalmente no que se refere à complexidade”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 145. 
 
A respeito da teoria das estruturas hierárquicas de Chomsky e de sua 
aplicabilidade quanto às linguagens, analise as afirmativas a seguir e 
assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) As gramáticas livres de contexto ou tipo 2 apresentam como desafios 
as múltiplas ocorrências de um mesmo trecho de programa. 
II. ( ) As gramáticas sensíveis ao contexto ou tipo 1 apresentam a 
associação de um significado (semântica) a partir do código de um 
programa. 
III. ( ) O estudo da classe das linguagens livres do contexto permite uma 
representação simples da sintaxe tanto para linguagens artificiais como para 
linguagens naturais. 
IV. ( ) As gramáticas de grafos têm como ideia fundamental: regras de 
produção ímpares, formadas por grafos. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
Resposta Selecionada: 
V, V, V, F. 
Resposta Correta: 
V, V, V, F. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. De fato, as gramáticas 
livres de contexto ou tipo 2 apresentam como desafios as múltiplas 
 
ocorrências de um mesmo trecho de programa. Essas são 
características das gramáticas livres de contexto ou tipo 2. Já as 
gramáticas sensíveis ao contexto ou tipo 1 apresentam a associação 
de um significado (semântica) a partir do código de um programa. 
Por definição, esse é o comportamento esperado delas. Logo, o 
estudo da classe das linguagens livres do contexto permite uma 
representação simples da sintaxe tanto para linguagens artificiais 
como para linguagens naturais. 
 
 Pergunta 7 
1 em 1 pontos 
 
Observe a figura na sequência, que apresenta a ilustração de um autômato 
finito construído a partir da gramática G, com três conexões, à direita, qf, à 
esquerda, S e, embaixo, B. Verifique, portanto, a respectiva ilustração 
quanto ao fluxo de conexões do autômato finito. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. 
 
 
Fonte: Menezes (2015, p. 102). 
#PraCegoVer : a figura apresenta um autômato finito construído a partir da 
gramática G, sendo M = ({ a, b }, { S, A, B, qf }, δ, S, { qf }), em que G = ({ S, 
A, B }, { a, b }, P, S). O respectivo autômato apresenta três conexões, à 
direita, qf, à esquerda, S e, embaixo, B. Essas conexões estão 
representadas por círculos: três círculos alinhados na horizontal e um círculo 
abaixo do círculo central com setas indicando justamente as conexões. 
Considerando a figura ilustrada, a fim de apresentar o funcionamento do 
teorema do bombeamento para linguagens regulares utilizando autômatos, 
analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para 
a(s) Falsa(s). 
 
I. ( ) Caso o autômato reconheça uma entrada (S) de comprimento maior ou 
igual ao número de estados (n), obrigatoriamente, o autômato assumirá 
algum estado (q) mais de uma vez. 
II. ( ) Caso o autômato assuma algum estado (q) mais de uma vez, 
 
verificamos, então, que existe um ciclo na função programa que passa por 
(q); assim, o bombeamento é executado zero ou mais vezes. 
III. ( ) O teorema do bombeamento não garante que os formalismos 
regulares são capazes de expressar diversos tipos de bombeamento, por 
exemplo: duplo bombeamento ou triplo bombeamento. 
IV. ( ) O teorema do bombeamento é diferente do lema do bombeamento 
para linguagens regulares, pois este descreve as propriedades essenciais 
de todas as linguagens regulares. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, F. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. A afirmativa I é 
verdadeira, porque dada uma entrada (S) de comprimento maior ou 
igual ao número de estados (n), obrigatoriamente, por definição, 
teremos que o autômato assumirá algum estado (q) mais de uma 
vez. A afirmativa II também é verdadeira, pois, assumindo mais de 
uma vez algum estado (q), existirá um ciclo na função programa 
que passa por (q); logo, teremos o bombeamento executado zero ou 
mais vezes. 
 
 
 Pergunta 8 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“As expressões regulares são consideradas adequadas para a comunicação 
humano com humano e, principalmente, para a comunicação humano com 
máquina, por meio de operações matemáticas e de propriedades de 
concatenação e união; logo, as expressões regulares sempre buscaram 
explicar matematicamente o funcionamento de uma linguagem, a partir da 
teoria dos conjuntos”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 96. 
 
Sobre as propriedades das expressões regulares, analise as afirmativas a 
seguir: 
 
I. Uma expressão regular vazia parte do pressuposto de haver uma 
linguagem vazia. 
II. Dada uma expressão regular, que deriva de uma linguagem regular vazia, 
a partir da inserção do elemento “x”, a linguagem não será mais vazia e terá 
como elemento único “x”. 
III. Dado (r) e (s) como expressões regulares, com as respectivas 
linguagens R e S, caso quiséssemos realizar a operação de união, teríamos 
 
a expressão: (r*s). 
IV. Dado (r) e (s) como expressões regulares, com as respectivas 
linguagens R e S, caso quiséssemos realizar a operação de concatenação, 
teríamos a expressão: (r+s). 
 
Está correto o que se afirma em: 
Resposta Selecionada: 
I e II, apenas. 
Resposta Correta: 
I e II, apenas. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, porque uma expressão 
regular vazia deriva, necessariamente, de uma linguagem vazia; da 
mesma forma, uma dada expressão regular, que deriva de uma 
linguagem vazia, a partir do momento em que ocorre a inserção de 
um elemento “x”, não será mais vazia e terá como elemento único: 
“x”. Assim, quando temos uma linguagem vazia, a sua expressão 
regular será vazia, sem elementos. Desse modo, um elemento novo 
a ser inserido preencherá a linguagem; esta, por sua vez, não estará 
mais vazia. 
 
 
 Pergunta 9 
0 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: 
 
A asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. 
 
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: 
Sua resposta está incorreta. A alternativa está incorreta, pois ambasas asserções, isto é, asserção I e asserção II, são proposições 
verdadeiras, uma vez que o conjunto finito de todas as palavras, em 
uma linguagem formal, é o que origina a 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. Essas regras, quando 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 10 
1 em 1 pontos 
 
Leia o excerto a seguir: 
“Na operação de união de expressões regulares r e s, temos a expressão: (r 
+ s), que é uma expressão regular derivada da operação de união e denota 
a linguagem: R ∪ S. Já na concatenação, temos a expressão (rs), que é 
uma expressão regular e denota a linguagem: R S = { uv ⏐ u ∈ R e v ∈ S }”. 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas 
universais e computabilidade. Porto Alegre: Grupo A, 2011. p. 105. 
 
A respeito da teoria dos conjuntos e de sua aplicabilidade quanto às 
expressões regulares para criação de linguagens, analise as afirmativas a 
seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) A expressão regular aa deriva de uma linguagem com inclusão 
somente do elemento aa no conjunto de uma linguagem. 
II. ( ) A expressão regular ba* deriva de uma linguagem com todas as 
palavras que iniciam por b, seguida por zero ou mais a. 
III. ( ) A expressão regular (a+b)* deriva de todas as palavras sobre (b), mas 
não sobre (a). 
IV. ( ) A expressão regular (b+a)* deriva de todas as palavras sobre (a), mas 
não sobre (b). 
 
Assinale a alternativa que apresenta a sequência correta. 
 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, F. 
 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta. A expressão ‘aa’, de 
fato, deriva de uma linguagem com inclusão somente do elemento 
‘aa’ dentro do conjunto de uma linguagem. Já a expressão regular 
ba* deriva de uma linguagem com todas as palavras que se iniciam 
com b, com zero ou com a. Assim, visto que ‘aa’ é um elemento 
que pertence ao conjunto da linguagem, este, por sua vez, já traz a 
expressão ‘aa’, como pontuado. Já a expressão ba* delimita todas 
as palavras que são iniciadas com b, zero ou com a, por definição.