Atividade 2- Linguagens Formais E Autômatos

Prévia do material em texto

19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 1/7
Resultado da tentativa 8 em 10 pontos 
Tempo decorrido 2 horas, 0 minuto
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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?
Trata-se de restrições lógicas sobre a forma de produção de uma linguagem
regular.
Trata-se de restrições lógicas sobre a forma de produção de uma
linguagem regular.
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.
Pergunta 2
Resposta Selecionada: 
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 Vpara 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.
V, V, F, F.
1 em 1 pontos
1 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 2/7
Resposta Correta: 
Comentário
da resposta:
V, V, F, F.
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 3
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
Sua resposta está incorreta. A alternativa está incorreta, pois ambas as asserções,
isto é, asserção I e asserção II, são proposições verdadeiras, uma vez que 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 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 4
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
0 em 1 pontos
1 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 3/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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:
I, II e IV, apenas.
I, II e IV, apenas.
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 5
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
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?
Um formalismo que expressa a construção de uma linguagem regular.
Um formalismo que expressa a construção de uma linguagem
regular.
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 6
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”.
1 em 1 pontos
1 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 4/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
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:
I e II, apenas.
I e II, apenas.
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 7
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
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?
Trata-se de uma classificação hierárquica das gramáticas formais com 4
níveis.
Trata-se de uma classificação hierárquica das gramáticas formais
com 4 níveis.
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.
1 em 1 pontos
1 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 5/7
Pergunta 8
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa
correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
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 9
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. 
0 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 6/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, F, V.
V, V, F, V.
Sua resposta está incorreta. A alternativa está incorreta, pois a expressão regular
(bb) é responsável por concatenar a linguagem gerada contendo somente a
palavra bb, por definição das regras de expressões regulares, e não somente a
palavra b; logo, podemos afirmar que a afirmativa III é falsa.
Pergunta 10
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
1 em 1 pontos
19/09/2021 17:22 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 7/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, V, F.
F, V, V, F.
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.