QUESTIONÁRIO UNIDADE 1 Linguagens Formais e Autômatos

Prévia do material em texto

4/20/23, 9:01 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93386007_1&course_id=_288578_1&content_id=_… 1/5
 Revisar envio do teste: QUESTIONÁRIO UNIDADE ILINGUAGENS FORMAIS E AUTOMATOS 7938-30_43701_R_E1_20231 CONTEÚDO
Usuário
Curso LINGUAGENS FORMAIS E AUTOMATOS
Teste QUESTIONÁRIO UNIDADE I
Iniciado
Enviado
Status Completada
Resultado da tentativa 5 em 5 pontos  
Tempo decorrido 1 hora, 22 minutos
Resultados exibidos Todas as respostas, Respostas enviadas, Respostas corretas, Comentários, Perguntas respondidas incorretamente
Pergunta 1
Resposta Selecionada: b. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da resposta:
Considere o autômato �nito indicado na imagem, no qual o estado inicial é o estado 0 e o estado �nal é o estado 1. Este autômato é o
reconhecedor de uma Linguagem Regular. Ao executá-lo tendo como entrada a cadeia "klnl", a execução irá terminar no estado:
2.
1.
2.
3.
4.
5.
Resposta: B
Comentário: as transições de estados ao percorrer a cadeia dada serão, respectivamente, 1, permanece em 1, 3 e 2.
Pergunta 2
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Uma gramática pode ser representada por um conjunto de parâmetros. Assinale a alternativa que não indica corretamente um dos parâmetros
constituintes de uma gramática:
N: conjunto das cadeias que podem ser de�nidas pela gramática.
P: conjunto das regras de substituição que constituem a gramática.
V: conjunto dos símbolos terminais do alfabeto da gramática.
S: símbolo não terminal raiz da gramática.
N: conjunto das cadeias que podem ser de�nidas pela gramática.
Σ: conjunto dos símbolos não terminais do alfabeto da gramática.
Resposta: D
Comentário: uma gramática é de�nida por quatro parâmetros, V, Σ, P e S, que correspondem às descrições resumidas
das demais alternativas da questão.
UNIP EAD BIBLIOTECAS MURAL DO ALUNO TUTORIAIS
eduardo.fernandes14 @aluno.unip.br 1
CONTEÚDOS ACADÊMICOS
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=_10_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=_25_1
https://ava.ead.unip.br/webapps/login/?action=logout
4/20/23, 9:01 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93386007_1&course_id=_288578_1&content_id=_… 2/5
Pergunta 3
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere a Linguagem Regular de�nida pela gramática a seguir, sendo S a raiz:
 
V = {1, 2, 3}
Σ = {S, A, C}
P= {S →
1S, S → A, A → 23C, A → 33C, A →
3C, C → 1C, C → ε}
 
Qual das cadeias a seguir não pertence a esta linguagem?
13331111.
1113.
133.
1111311.
13331111.
3.
Resposta: D
Comentário: se observarmos a quarta e quinta regras de substituição, as cadeias formadas terão apenas um ou dois
símbolos “3”. Assim, uma cadeia com três “3” não pode ser formada.
Pergunta 4
Resposta Selecionada: b. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere a Linguagem Regular L de�nida pela expressão regular L = x*(y+z)x(y)*. Qual das cadeias a seguir não pertence a esta linguagem?
xyxxy.
xzx.
xyxxy.
xyxy.
zx.
xxyxy.
Resposta: B
Comentário: as cadeias formadas por esta expressão regular terão o formato "(0 ou mais x)yx(0 ou mais y)" ou formato "
(0 ou mais x)zx(0 ou mais y)". A cadeia xyxxy é a única que não corresponde a u7m destes dois formatos.
Pergunta 5
Resposta
Selecionada:
a. 
Respostas: a. 
b. 
c. 
d. 
e.
Comentário da
resposta:
Considere o Fecho de Kleene indicado por (9+8)* e assinale a alternativa correta:
Este fechamento pode gerar cadeias que comecem com o símbolo 9 ou com o símbolo 8.
Este fechamento pode gerar cadeias que comecem com o símbolo 9 ou com o símbolo 8.
Não é possível gerar a cadeia vazia a partir deste fechamento.
Apenas cadeias que comecem com o símbolo 9 podem ser geradas a partir deste fechamento.
Apenas cadeias que comecem com o símbolo 8 podem ser geradas a partir deste fechamento.
Em qualquer cadeia não vazia gerada por este fechamento, teremos sempre um símbolo 8 imediatamente na sequência
de todo símbolo 9.
Resposta: A
Comentário: esta expressão regular permite gerar qualquer combinação possível dos símbolos 8 e 9, em qualquer
ordem, incluindo uma cadeia vazia (zero símbolos 8 e 9).
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/20/23, 9:01 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93386007_1&course_id=_288578_1&content_id=_… 3/5
Pergunta 6
Resposta Selecionada: c. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Analise as a�rmações a seguir acerca de Gramáticas Regulares:
 
I. Toda Gramática regular à direita possui suas regras de substituição como sendo a substituição de um símbolo não terminal por um símbolo
terminal ou por um par não terminal/terminal, nesta ordem.
II. Toda Gramática regular à esquerda possui suas regras de substituição como sendo a substituição de um símbolo não terminal por um
símbolo terminal ou por um par terminal/não terminal, nesta ordem.
III. Toda Gramática Linear à esquerda possui uma gramática equivalente à direita e vice-versa.
 
Estão corretas as a�rmações:
III, apenas.
I e II, apenas.
I e III, apenas.
III, apenas.
II e III, apenas.
I, II e III.
Resposta: C
Comentário: as de�nições das gramáticas nas a�rmações I e II estão invertidas, a I descreve gramáticas à esquerda e a
II, gramáticas à direita.
Pergunta 7
Resposta
Selecionada:
e.
Respostas: a. 
b. 
c. 
d.
e.
Comentário da
resposta:
Em 1959, Noam Chomsky apresentou uma hierarquia das Linguagens, a qual leva seu nome (Hierarquia de Chomsky). Indique a alternativa em
relação a esta hierarquia:
As Linguagens de Programação normalmente se encontram em formas que correspondem aos Tipos 2 e 3 da
Hierarquia.
As Linguagens Humanas (Linguagens Naturais) são classi�cadas como o Tipo 3, por serem as mais complexas.
A maioria das Linguagens de Programação encontram-se no Tipo 1, que correspondem às Linguagens Irrestritas.
As Linguagens Regulares são do tipo 2, por serem mais complexas que as Linguagens Livres de Contexto.
Na prática, o tipo mais restrito de Linguagens, as de tipo 3, acabam por não existirem, sendo apenas uma ferramenta
teórica.
As Linguagens de Programação normalmente se encontram em formas que correspondem aos Tipos 2 e 3 da
Hierarquia.
Resposta: E
Comentário: as Linguagens de Programação, na sua maioria, são Regulares ou Livres de Contexto. Linguagens Naturais
são do Tipo I. A imagem a seguir mostra esta hierarquia:
Pergunta 8
Sabendo que o autômato �nito da imagem possui estado inicial igual a 0, e estados �nais iguais a 0 e 1, a gramática regular que ele veri�ca é:
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/20/23, 9:01 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93386007_1&course_id=_288578_1&content_id=_… 4/5
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
(a+b)*(c+d)*.
(c+d)* (a+b)*.
(a+b)*ca.
(a+b)(c+d)*.
(a)*(c+d)*.
(a+b)*(c+d)*.
Resposta: E
Comentário: a primeira transição de 0 para 0 representa (a+b)*. A transição de 0 para 1 e de 1 para 1 identi�cam
(c+d)*.
Pergunta 9
Resposta Selecionada: a.Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Sabendo que o autômato �nito da imagem possui estado inicial igual a 0 e estado �nal igual a 2, ao analisarmos a cadeia 0322222, podemos
concluir que ela:
Será aceita, terminando no estado 2.
Será aceita, terminando no estado 2.
Será rejeitada, terminando no estado 2.
Será rejeitada, terminando no estado 1.
Será rejeitada, terminando no estado 0.
Será rejeitada, terminando no estado 3.
Resposta: A
Comentário: as transições de estado para cada símbolo da cadeia serão respectivamente: 1,1, 2, 2, 2, 2, 2 (estado �nal
de aceitação).
Pergunta 10
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
d. 
Considere a Linguagem Regular de�nida pela gramática a seguir, sendo S a raiz:
 
V = {p, q, r}
Σ = {S, A, C}
P= {S → pS, S → A, A → qqB, B → rB, B → ε}
 
A expressão regular correspondente é:
p*qqr*.
p*qr*.
pq*r.
pqr.
pqqr.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
4/20/23, 9:01 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_93386007_1&course_id=_288578_1&content_id=_… 5/5
Quinta-feira, 20 de Abril de 2023 21h01min05s GMT-03:00
e. 
Comentário da
resposta:
p*qqr*.
Resposta: E
Comentário: as duas primeiras regras de transição indicam um fechamento de p; a segunda indica uma concatenação
de dois q´s; e, por �m, as duas últimas indicam um fechamento de r.
← OK