QUESTIONÁRIO 2 - Linguagens Formais e Autômatos

Prévia do material em texto

4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 1/7
 
Revisar envio do teste: QUESTIONÁRIO UNIDADE II
LINGUAGENS FORMAIS E AUTOMATOS 7938-30_43701_R_E1_20231 CONTEÚDO
Usuário
Curso LINGUAGENS FORMAIS E AUTOMATOS
Teste QUESTIONÁRIO UNIDADE II
Iniciado 22/04/23 14:40
Enviado 27/04/23 15:23
Status Completada
Resultado da
tentativa
5 em 5 pontos  
Tempo decorrido 120 horas, 42 minutos
Resultados exibidos Todas as respostas, Respostas enviadas, Respostas corretas, Comentários, Perguntas
respondidas incorretamente
Pergunta 1
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário
da resposta:
Complete as lacunas na a�rmação a seguir:
 
"As expressões regulares não conseguem representar completamente as Linguagens Livres de
Contexto devido à ocorrência de ______(I)_______ na construção das cadeias destas; assim, para
representar as regras de substituição destas gramáticas utiliza-se ________(II)_________."
I: Encadeamentos; II: o Formalismo de Backus-Naur.
I: Encadeamentos; II: o Formalismo de Backus-Naur.
I: Encadeamentos; II: a Máquina de Turing.
I: Fechos de Kleene; II: a Máquina de Turing.
I: Fechos de Kleene; II: o Formalismo de Backus-Naur.
I: Encadeamentos; II: Autômatos Finitos.
Resposta: A
Comentário: a representação das Linguagens do Tipo 2 na Hierarquia de
Chomsky precisa de outra forma de representação. O Formalismo de
Backus-Naur não tem a força matemática das Expressões Regulares, mas
permite representar uma gramática de uma forma mais sucinta do que
as formas usuais.
Pergunta 2
CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNO TUTORIAISUNIP EAD
0,5 em 0,5 pontos
0,5 em 0,5 pontos
http://company.blackboard.com/
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_288578_1
https://ava.ead.unip.br/webapps/blackboard/content/listContent.jsp?course_id=_288578_1&content_id=_3406919_1&mode=reset
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_25_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_27_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_47_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_29_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_10_1
https://ava.ead.unip.br/webapps/login/?action=logout
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 2/7
Resposta Selecionada: b. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Analise as a�rmações acerca do Formalismo de Backus-Naur:
 
I. Só pode ser utilizado para gramáticas livres de contexto
II. Diferente das expressões regulares, não se baseia em operações, sendo apenas uma
forma mais simpli�cada de representar uma gramática.
III. Gramáticas representadas nesta forma não podem ser representadas na forma de um
autômato.
 
Estão corretas:
A a�rmação II apenas.
As a�rmações I e III.
A a�rmação II apenas.
A a�rmação III apenas.
As a�rmações II e III.
Todas as a�rmações.
Resposta: B
Comentário: a forma de Backus-Naur pode ser utilizada tanto para
gramáticas livres de contexto quanto para gramáticas regulares. Estas
gramáticas podem ser representadas por autômatos, �nitos ou de pilha,
dependendo das características da linguagem.
Pergunta 3
Resposta
Selecionada:
e.
Respostas: a.
b.
c.
d.
Em relação à memória auxiliar em um Autômato (�nito ou de pilha), assinale a alternativa
correta:
Pode não ser necessária em um autômato �nito, dependendo da
gramática correspondente.
Sempre assumirá a forma de uma pilha como estrutura de dados, para
qualquer autômato.
Se assumir a forma de uma pilha, o autômato só poderá ser
empregado exclusivamente para Linguagens do Tipo 2 (Linguagens
Livres de Contexto).
Seu uso só é necessário pra Linguagens do Tipo 1 (Linguagens
sensíveis ao contexto).
Qualquer tipo de autômato sempre necessitará de uma memória
auxiliar, independente da forma desta.
0,5 em 0,5 pontos
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 3/7
e.
Comentário da
resposta:
Pode não ser necessária em um autômato �nito, dependendo da
gramática correspondente.
Resposta: E
Comentário: autômatos �nitos, determinísticos ou não, não precisam
de uma memória auxiliar; porém, está é necessária na construção dos
autômatos de pilha, na forma da própria pilha.
Pergunta 4
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere a Hierarquia de Chomsky como apresentada na imagem. Um Autômato de Pilha
pode ser utilizado como reconhecedor para uma gramática:
Dos tipos 2 e 3.
Dos tipos 1, 2 e 3.
Do tipo 1, apenas.
Do tipo 2, apenas.
Do tipo 3, apenas.
Dos tipos 2 e 3.
Resposta: E
Comentário: autômatos de pilha podem ser utilizados como
reconhecedores tanto para Linguagens Livres de Contexto quanto
para Linguagens Regulares.
Pergunta 5
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 4/7
Resposta
Selecionada:
d.
Respostas: a.
b.
c.
d.
e.
Comentário
da resposta:
Uma Linguagem Irrestrita apresenta como característica das regras de substituição da sua
gramática:
Qualquer substituição é possível desde que do lado esquerdo exista pelo
menos um símbolo não terminal e também que o lado direito possua
uma quantidade de símbolos não inferior àquela encontrada no lado
esquerdo da mesma regra.
Um símbolo terminal só pode ser substituído por um par de símbolos,
sendo um deles terminal e outro não terminal (em qualquer ordem).
Um símbolo terminal só pode ser substituído por um aninhamento
contendo um símbolo terminal, um não terminal e outro terminal, nesta
ordem.
Qualquer substituição é possível desde que do lado esquerdo da regra
haja ao menos um símbolo não terminal.
Qualquer substituição é possível desde que do lado esquerdo exista pelo
menos um símbolo não terminal e também que o lado direito possua
uma quantidade de símbolos não inferior àquela encontrada no lado
esquerdo da mesma regra.
Qualquer substituição é possível desde que sem nenhum tipo de
restrição (daí o nome irrestrita).
Resposta: D
Comentário: as gramáticas irrestritas, apesar do nome, não aceitam
quaisquer regras de substituição: os símbolos que estão substituídos
devem conter ao menos um símbolo não terminal, e a substituição deve
ser feita por uma quantidade maior ou igual de símbolos (não pode haver
diminuição do número de símbolos na cadeia que está sendo formada).
Pergunta 6
Resposta
Selecionada:
c. 
Respostas: a.
b.
c. 
d.
Indique a alternativa incorreta sobre Máquinas de Turing.
É uma estrutura necessariamente não determinística.
A �ta de entrada é sempre in�nita à direita, podendo, em alguns
casos, também ser in�nita à esquerda.
O cursor pode avançar e retroceder na �ta, conforme o valor lido.
É uma estrutura necessariamente não determinística.
O cursor pode gravar na �ta de entrada, alterando seu conteúdo.
0,5 em 0,5 pontos
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 5/7
e. 
Comentário da
resposta:
É uma forma de representar um algoritmo computacional.
Resposta: C
Comentário: Máquinas de Turing, como avançam ou retrocedem de
acordo com valor lido na �ta, não podem ser não determinísticas.
Pergunta 7
Resposta
Selecionada:
c.
Respostas: a.
b.
c.
d.
e.
Comentário da
resposta:
Indique a alternativa corretasobre Autômatos Finitos não Determinísticos.
Uma transição pode ser feita de um estado para vários estados
distintos.
É equivalente ao Autômato Finito Determinístico, porém com uma
pilha associada.
É uma forma mais elaborada dos Autômatos Finitos Determinísticos,
possuindo sempre maior quantidade de estados e regras de transição.
Uma transição pode ser feita de um estado para vários estados
distintos.
Sendo não determinísticos, suas transições são baseadas em
probabilidades.
Este tipo de autômato não é aplicável para o reconhecimento de
Linguagens Regulares.
Resposta: C
Comentário: as funções de transição deste tipo de autômato não
contêm apenas um único estado “seguinte”, podendo conter um
conjunto de próximos estados.
Pergunta 8
Resposta
Selecionada:
a.
As Gramáticas Livres de Contexto apresentam o conceito de aninhamento nas suas regras
de substituição. Isto signi�ca que:
Um símbolo não terminal é substituído por um símbolo terminal, um
não terminal e outro terminal, nesta ordem.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 6/7
Respostas: a.
b.
c.
d.
e.
Comentário da
resposta:
Um símbolo não terminal é substituído por um símbolo terminal, um
não terminal e outro terminal, nesta ordem.
Um símbolo não terminal é substituído por um par de símbolos
terminais.
Um símbolo terminal é substituído por um par de símbolos, sendo
um terminal e outro não terminal, nesta ordem.
Um símbolo terminal é substituído por um par de símbolos, sendo
um não terminal e outro terminal, nesta ordem.
Um símbolo não terminal é substituído por um par de símbolos não
terminais.
Resposta: A
Comentário: uma regra de substituição que contenha um aninhamento
irá substituir um símbolo não terminal por um símbolo terminal, um
não terminal e outro terminal, nesta ordem.
Pergunta 9
Resposta Selecionada: b. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Uma Máquina de Turing com �ta limitada à esquerda irá reconhecer Linguagens:
Dependentes do Contexto, Livres de Contexto e Regulares.
Dependentes do Contexto, Livres de Contexto e Irrestritas.
Dependentes do Contexto, Livres de Contexto e Regulares.
Livres de Contexto e Regulares.
Livres de Contexto e Irrestritas.
De qualquer tipo.
Resposta: B
Comentário: Máquinas de Turing com �ta limitada reconhecem as
Dependentes do Contexto (Tipo 1), Livres de Contexto (Tipo 2) e
Regulares (Tipo 3).
Pergunta 10
Analise as a�rmações acerca dos Autômatos de Pilha:
 
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/27/23, 3:23 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93436369_1&course_id=_288578_1&content_id=_… 7/7
Quinta-feira, 27 de Abril de 2023 15h23min07s GMT-03:00
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
I. Podem ser determinísticos ou não determinísticos.
II. Possuem uma pilha e o elemento na posição de saída desta equivale ao estado do
autômato.
III. Podem ser utilizados para identi�car cadeias construídas por gramáticas livres de
contexto e regulares.
 
Estão corretas:
As a�rmações II e III.
As a�rmações I e III.
A a�rmação II apenas.
A a�rmação III apenas.
As a�rmações II e III.
Todas as a�rmações.
Resposta: D
Comentário: como a mudança de estado de um autômato de pilha é
empilhar ou desempilhar um símbolo na pilha, eles não podem ser não
determinísticos (não se empilha ou desempilha mais de um elemento
de uma só vez).
← OK