Atividade 2 - GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS UAM SET 2021

Prévia do material em texto

Curso GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01 
Teste ATIVIDADE 2 (A2) 
Iniciado 26/09/21 18:05 
Enviado 26/09/21 18:18 
Status Completada 
Resultado da tentativa 10 em 10 pontos 
Tempo decorrido 13 minutos 
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários 
• 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 
 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 3 
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 4 
1 em 1 pontos 
 Observe a figura a seguir, que apresenta uma ilustração das Expressões 
Regulares (ER) e dos seus autômatos correspondentes a zero operadores, 
ou seja, temos expressões regulares à esquerda, e os seus respectivos 
autômatos finitos a partir de zero operadores à direita: 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. 
 
Fonte: Menezes (2015, p. 125). 
#PraCegoVer : na ilustração, temos expressões regulares e seus 
respectivos autômatos finitos a partir de zero operadores. Na coluna à 
esquerda, temos as expressões regulares e, na coluna à direita, temos os 
autômatos finitos correspondentes. Temos, na coluna à esquerda, as 
respectivas expressões regulares, a partir de r com zero operadores; na 
primeira linha após o título, é apresentado r = ∅; na segunda linha, temos r=ε 
e, na terceira linha, temos r = x (x pertencente a Σ). Respectivamente, na 
coluna à direita, contendo os autômatos finitos correspondentes às 
expressões regulares, temos, na primeira linha, M1 = (∅, { q0 }, δ1, q0, ∅), 
M2 = (∅, { qf }, δ2, qf, { qf }) e M3 = ({ x }, { q0, qf }, δ3, q0, { qf }). 
Considerando a figura ilustrada, a fim de apresentar o esquema lógico das 
expressões regulares e autômatos, analise as afirmativas a seguir e 
assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) Em uma linguagem formal, as expressões são responsáveis pelo 
encadeamento lógico do comportamento da linguagem. 
II. ( ) Nas linguagens formais, as operações vão derivar dos respectivos 
autômatos finitos correspondentes e das gramáticas regulares. 
III. ( ) A expressão regular (bb) é responsável por concatenar a linguagem 
 
gerada contendo somente a palavra b. 
IV. ( ) A expressão regular (ab*) é responsável por concatenar a linguagem 
gerada com todas as palavras que iniciam com a. 
 
Assinale a alternativa que apresenta a sequência correta. 
Resposta Selecionada: 
 
V, V, F, V. 
Resposta Correta: 
 
V, V, F, V. 
Comentário 
da resposta: Resposta correta. A alternativa está correta, pois em uma 
linguagem formal, as expressões regulares têm por finalidade gerar 
o encadeamento lógico do comportamento da linguagem. Logo, nas 
linguagens formais, as operações vão derivar dos respectivos 
autômatos finitos e de suas gramáticas regulares correspondentes.Considerando que a expressão regular (ab*) é responsável por 
concatenar a linguagem por ela gerada, teremos como produto 
todas as palavras que iniciam com (a). 
 
 
• Pergunta 5 
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. 
 
• Pergunta 6 
1 em 1 pontos 
 Leia o excerto a seguir: 
“Quanto às estruturas das gramáticas regulares, é possível perceber nas 
gramáticas lineares uma forte restrição no formato das produções, no caso, 
o lado esquerdo possui exatamente uma variável, já o lado direito de uma 
produção é constituído por, no máximo, uma variável. Adicionalmente, essa 
variável, se existir, sempre antecede (linear à esquerda) ou sucede (linear à 
direita) qualquer subpalavra”. 
 
DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas 
universais e computabilidade. Porto Alegre: Grupo A, 2011. p. 110. 
 
Sobre as propriedades das gramáticas regulares, analise as afirmativas a 
seguir. 
 
I. Existe mais de uma maneira de restringir as regras de produção das 
linguagens, de forma a definir uma gramática regular. 
II. Podemos ter nas formas de estruturação das gramáticas regulares: 
gramáticas lineares à direita e gramáticas regulares à esquerda. 
III. A gramática linear unitária à direita é o único tipo possível de produção 
unitária das gramáticas lineares. 
IV. Por definição, seja G = (V, T, P, S) uma gramática. A linguagem gerada 
pela gramática G será L(G), tal que: L(G) = { w ∈ T* � S ⇒+ w }. 
 
Está correto o que se afirma em: 
 
Resposta Selecionada: 
 
I, II e IV, apenas. 
Resposta Correta: 
 
I, II e IV, apenas. 
Comentário 
da resposta: Resposta correta. A alternativa está correta, porque temos mais de 
uma forma de restrição quanto às regras de produção de 
linguagens no tocante às gramáticas regulares; logo, podemos, 
sim, ter tanto estruturas de gramáticas lineares à direita e à 
esquerda, por definição estrutural de qualquer gramática regular, 
dado G = (V, T, P, S) sendo uma gramática. A linguagem gerada 
pela gramática G será L(G), tal que: L(G) = { w ∈ T* � S ⇒+ w }. 
 
 
• Pergunta 7 
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 8 
1 em 1 pontos 
 Leia o excerto a seguir: 
“Na teoria da computação, é comum o emprego de autômatos finitos 
construídos a partir de gramáticas regulares, pois a própria elaboração de 
linguagens regulares permeia o emprego das gramáticas; logo, é importante 
perceber que a gramática é fundamental para implementação e construção 
do autômato finito”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
 
2015. p. 102. 
 
A respeito das gramáticas regulares e dos autômatos e de sua aplicabilidade 
nas expressões regulares, analise as afirmativas a seguir e assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) É possível haver uma gramática linear à esquerda e à direita, 
simultaneamente. 
II. ( ) Caso uma gramática seja linear à direita, a linguagem gerada será 
regular. 
III. ( ) Caso uma gramática seja linear à esquerda, a linguagem gerada não 
será regular. 
IV. ( ) Uma gramática regular não pode dar origem a um autômato finito não 
determinístico. 
 
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 gramática pode, 
simultaneamente, ser linear à esquerda e linear à direita. De fato, 
caso a gramática seja linear à direita, teremos uma linguagem 
regular sendo gerada, por definição da teoria das gramáticas 
regulares; caso ocorra uma gramática linear à esquerda, também 
teríamos uma linguagem regular sendo gerada. Logo, podem haver 
gramáticas lineares tanto à esquerda quanto à direita. 
 
 
• Pergunta 9 
1 em 1 pontos 
 Leia o excerto a seguir: 
“Uma das principais características das linguagens regulares é o fato de 
serem representadas por formalismos de pouca complexidade, grande 
eficiência e fácil implementação. A partir dessa lógica, você verá que nasce 
o teorema do bombeamento para as linguagens regulares”. 
 
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. O teorema do bombeamento para linguagens regulares adota duas 
variáveis por definição (q0) estado inicial e (qf) estado final. 
Pois:II. Se uma linguagem é regular, esta aceita um autômato finito 
determinístico, o qual possui um número finito e predefinido de estados. 
 
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 de fato, o teorema do 
bombeamento para linguagens regulares pressupõe as variáveis q0 
e qf, respectivamente, estado inicial e estado final. A asserção II 
também é uma proposição verdadeira e justifica a I, porque dado 
que uma linguagem regular aceita um autômato finito 
determinístico, este, por ser finito, possuirá um número delimitado e 
predefinido de estados. 
 
 
• Pergunta 10 
1 em 1 pontos 
 As gramáticas regulares são fundamentais para derivar formas estruturais 
que irão compor as linguagens regulares que serão criadas, ou seja, não 
cabe falar de linguagem regular sem gramática, tendo em vista que as 
regras que coordenam o encadeamento lógico das linguagens se derivam 
das gramáticas regulares. 
 
Diante do exposto, qual é a definição de gramática regular? 
 
Resposta 
Selecionada: 
Trata-se de restrições lógicas sobre a forma de produção de uma 
linguagem regular. 
Resposta Correta: 
 
Trata-se de restrições lógicas sobre a forma de produção de uma 
linguagem regular. 
Comentário 
da resposta: Resposta correta. A alternativa está correta, pois a definição de 
gramática regular abarca as restrições lógicas impostas no 
desenvolvimento e produção de uma linguagem regular; logo, o 
encadeamento lógico das linguagens se deriva das gramáticas 
regulares, que estruturam regras e restrições de funcionamento 
para a linguagem. 
 
 
Domingo, 26 de Setembro de 2021 18h19min09s BRT