Atividade 5 N2 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS UAM out 2021 nota 9 - questão 6 ou 10 está errada

Prévia do material em texto

09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 1/8
Informações do teste
Descrição
Instruções
Várias
tentativas
Não permitido. Este teste só pode ser feito uma vez.
Forçar
conclusão
Este teste pode ser salvo e retomado posteriormente.
Caso necessite a utilização do "EXCEL" clique no link ao lado ----------->
excel.xlsx
PERGUNTA 1
Leia o trecho a seguir: 
“Em 1936, Alonzo Church demonstrou a tese de Church, na qual afirmou que qualquer
função computável poderia ser processada através de uma máquina de Turing, dessa
forma, se criou a premissa de que sempre existirá um procedimento definido, no qual
uma máquina de Turing processará uma função computacional”. 
  
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 159. 
  
Considerando o excerto apresentado sobre as propriedades da máquina de Turing,
analise as afirmativas a seguir. 
  
I. É impossível apresentar formalmente se a máquina de Turing é, de fato, o modelo
mais genérico de dispositivo computacional. 
II. Todos os modelos conhecidos propostos após a máquina de Turing possuem, no
máximo, a mesma capacidade computacional da máquina de Turing. 
III. A tese de Church não foi assumida como uma hipótese para toda a teoria da
computação, razão pela qual não é empregada. 
IV. A máquina de Turing é um autômato cuja fita possui tamanho máximo e pode ser
usada simultaneamente como dispositivo de entrada e de saída. 
  
Está correto o que se afirma em:
II e III, apenas.
I, II e IV, apenas.
I, II e III, apenas.
I e II, apenas.
II, III e IV, apenas.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
https://anhembi.blackboard.com/bbcswebdav/pid-18832422-dt-content-rid-137476121_1/xid-137476121_1
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 2/8
PERGUNTA 2
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:
I e II, apenas.
II, III e IV, apenas.
I, II e III, apenas.
II e III, apenas.
I, II e IV, apenas.
1 pontos   Salva
PERGUNTA 3
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
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 3/8
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:
II e III, apenas.
I e II, apenas.
I, II e III, apenas.
I, II e IV, apenas.
II, III e IV, apenas.
PERGUNTA 4
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.
V, V, F, V.
V, F, V, V.
 
F, V, F, F.
F, V, F, V.
V, V, V, F.
1 pontos   Salva
PERGUNTA 5
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 4/8
PERGUNTA 5
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 estruturas externas e independentes à criação das linguagens
regulares.
Trata-se de um formalismo que expressa a construção das expressões regulares.
Trata-se de um formalismo que expressa a construção dos autômatos
determinísticos.
Trata-se de uma estrutura que expressa a construção de uma árvore de derivação.
PERGUNTA 6
Leia o excerto a seguir: 
“Em aplicações como compiladores e processadores de textos, é comum a
caracterização da derivação das palavras em estrutura de dados de árvore, partindo
da raiz, até as folhas. A estrutura de árvore em especial é fundamental para a teoria da
computação, porque a partir dela, estruturas de tomada de decisão podem ser
implementadas”. 
  
MENEZES, P. B. Linguagens formais e autômatos . 6. ed. Porto Alegre: Grupo A,
2010. v. 3, p. 128. 
  
A respeito da teoria das árvores de derivação e de sua aplicabilidade, analise as
afirmativas a seguir e assinale V para a(s) verdadeira(s) e 
F para a(s) falsa(s). 
  
I. ( ) Árvores dederivação são empregadas na elaboração de gramáticas livres de
contexto, tendo em vista sua característica de criar estruturas encadeadas. 
II. ( ) Em uma gramática livre do contexto, uma única árvore de derivação pode
caracterizar derivações diferentes de uma mesma palavra. 
III. ( ) Na esquematização de uma árvore de derivação, temos a raiz, o vértice exterior,
o vértice interior e as folhas, que podem ser à direita e à esquerda. 
IV. ( ) Uma gramática livre do contexto apresenta como característica a derivação de
palavras na forma de árvore, denominada árvore de derivação. 
  
Assinale a alternativa que apresenta a sequência correta:
V, F, V, V.
F, V, F, F.
F, V, F, V.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 5/8
V, V, F, F.
V, V, F, V.
PERGUNTA 7
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 ( ) A á i d f ã i i l d á i
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 6/8
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.
V, V, F, V.
V, F, F, V.
F, F, V, F.
F, V, V, F.
V, V, F, F.
PERGUNTA 8
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.
F, V, F, V.
F, V, F, F.
V, F, V, V.
 
V, V, F, V.
V, V, F, F.
1 pontos   Salva
PERGUNTA 9
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 7/8
PERGUNTA 9
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:
I, II e IV, apenas.
I e II, apenas.
II, III e IV, apenas.
II e III, apenas.
I, II e III, apenas.
PERGUNTA 10
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.
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.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
09/10/2021 08:27 Fazer teste: 20212 - PROVA N2 (A5) – GRA0823 LINGUAGENS ...
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_73… 8/8
Quando temos uma ocorrência de um nome em um código que é tratado de forma
fácil, temos um problema sintático somente.
A análise sintática pode ser vista como um tipo especial de análise léxica, que é
centrada em componentes complexos da linguagem.
As linguagens formais se preocupam com os problemas sintáticos da linguagem e,
também, com os problemas léxicos.
Um programa considerado sintaticamente correto ou válido é um programa com
um código em uma linguagem adequada e que é esperado pelo programador ao
escrevê-lo. 
 
 Estado de Conclusão da Pergunta: