GRA0823 LINGUAGENS FORMAIS E AUTÔMATOSsemana 2

Prévia do material em texto

08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 1/8
Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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:
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 2
Resposta
Selecionada:
 
Resposta Correta: 
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.
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 2/8
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
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.
 
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 3/8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
Assinale a alternativa que apresenta a sequência correta.
V, V, F, V.
V, V, F, V.
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 4
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.
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 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 5
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
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 4/8
Resposta
Selecionada:
 
Resposta
Correta:Comentário
da resposta:
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 6
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.
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 5/8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
 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.
Pergunta 7
Leia o excerto a seguir:
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 6/8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
“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.
V, V, F, F.
V, V, F, F.
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 8
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.
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 7/8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
Assinale a alternativa que apresenta a sequência correta.
V, V, V, F.
V, V, V, F.
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 9
Resposta
Selecionada:
 
Resposta
Correta:
 
Comentário
da resposta:
Leia o excerto a seguir:
“Podemos, então, definir que um alfabeto é um conjunto finitode 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.
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. 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 10
Leia o excerto a seguir:
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:51 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 8/8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
“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:
I, II e III, apenas.
I, II e III, apenas.
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.