Buscar

gabarito P1 2014-1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 4 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

P1 — Linguagens Formais e Teoria da Computac¸a˜o, 2014.1
Prof. Christiano Braga
Instituto de Computac¸a˜o
Universidade Federal Fluminense
04/14/2014
Gabarito
1. (6 pontos) Considere e expressa˜o regular (a+ b)∗.
(a) (1 ponto) Descreva graficamente a func¸a˜o de transic¸a˜o do autoˆmato finito com transic¸o˜es vazias
(transic¸o˜es �) que reconhece a linguagem da expressa˜o regular dada. (Nota: Utilize o mapeamento
entre expresso˜es regulares a` autoˆmatos finitos com transic¸o˜es vazias apresentado em sala de aula.)
Resposta:
q2
a // q3
�
 
// q0
� //
�
��
q1
�
>>
�
 
q6
� //
�
WW
qf
q4
b // q5
�
>>
(b) (2 pontos) Calcule, equacionalmente, δ� (fecho-�) de cada estado do autoˆmato do item 1a.
Resposta:
δ�(q0) = {q0} ∪ δ(q0, �) ∪
⋃
p∈δ(q0,�)
δ�(p) = (1)
= {q0} ∪ {q1, qf} ∪ {q2, q4} = {q0, q1, q2, q4, qf}
δ�(q1) = {q1} ∪ δ(q1, �) ∪
⋃
p∈δ(q1,�)
δ�(p) = {q1, q2, q4} (2)
δ�(q2) = {q2} ∪ δ(q2, �) ∪
⋃
p∈δ(q2,�)
δ�(p) = {q2} (3)
δ�(q3) = {q3} ∪ δ(q3, �) ∪
⋃
p∈δ(q3,�)
δ�(p) = (4)
= {q3} ∪ {q6} ∪ δ�({q6}) =
= {q3} ∪ {q6} ∪ ({q6} ∪ {q1, qf} ∪ δ�(q1) ∪ δ�(qf )) =
= {q3} ∪ {q6} ∪ {q1, qf} ∪ {q1, q2, q4} ∪ {qf} = {q1, q2, q3, q4, q6, qf}
δ�(q4) = {q4} ∪ δ(q4, �) ∪
⋃
p∈δ(q4,�)
δ�(p) = {q4} (5)
δ�(q5) = {q5} ∪ {q6} ∪ ({q6} ∪ {q1, qf} ∪ δ�(q1) ∪ δ�(qf )) = (6)
= {q1, q2, q4, q5, q6, qf}
δ�(q6) = {q6} ∪ {q1, qf} ∪ δ�(q1) ∪ δ�(qf ) = {q1, q2, q4, q6, qf} (7)
δ�(qf ) = {qf} (8)
(c) (2 pontos) Calcule, equacionalmente, δ∗({q}, a), para cada q ∈ QM , e a ∈ ΣM , onde M e´ o
AFN � do item 1a.
Resposta:
δ∗({q0}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q0}, �)}) (9)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗� ({q0})})
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q0, q1, q2, q4, qf}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q0}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ δ∗({q0}, �)}) (10)
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
δ∗({q1}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q1}, �)}) (11)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q1, q2, q4}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q1}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q1, q2, q4}}) (12)
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
δ∗({q2}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q2}, �)}) (13)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q2}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q2}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q2}}) = ∅ (14)
δ∗({q3}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q3}, �)}) (15)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q1, q2, q3, q4, q6, qf}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q3}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ δ∗({q3}, �)}) (16)
= δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q1, q2, q3, q4, q6, qf}})
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
δ∗({q4}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q4}}) = ∅ (17)
δ∗({q4}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ δ∗({q4}, �)}) (18)
= δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q4}})
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
2
δ∗({q5}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q5}, �)}) (19)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q1, q2, q4, q5, q6, qf}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q5}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ δ∗({q3}, �)}) (20)
= δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q1, q2, q4, q5, q6, qf}})
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
δ∗({q6}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ δ∗({q6}, �)}) (21)
= δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {q1, q2, q4, q6, qf}})
= δ∗� ({q3})
= {q1, q2, q3, q4, q6, qf}
δ∗({q6}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ δ∗({q6}, �)}) (22)
= δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {q1, q2, q4, q6, qf}})
= δ∗� ({q5})
= {q1, q2, q4, q5, q6, qf}
δ∗({qf}, a) = δ∗� ({r | r ∈ δ(s, a) ∧ s ∈ {qf}}) = ∅ (23)
δ∗({qf}, b) = δ∗� ({r | r ∈ δ(s, b) ∧ s ∈ {qf}}) = ∅ (24)
(d) (1 ponto) Identifique os estados finais do autoˆmato finito na˜o-determinı´stico que reconhece a lin-
guagem da expressa˜o regular dada. Justifique sua resposta.
Resposta:
FAFN = {q | q ∈ QAFN � ∧ ((δ�(q) ∩ FAFN �) 6= ∅)} = {q0, q3, q5, q6, qf}
2. (2 pontos) Uma loja virtual, ao receber um pedido de compra pelo seu site, simultaneamente aguarda a
confirmac¸a˜o de pagamento do cliente e solicita ao seu estoque que prepare o(s) produto(s) solicitado(s)
para entrega. Uma vez pronto para a entrega, o produto e´ enviado ao cliente, independentemente da
confirmac¸a˜o de pagamento, que pode ou na˜o ter sido realizada.
(a) (1 ponto) Represente o comportamento da loja virtual, descrito acima, como um autoˆmato finito,
detalhando cada um dos seus componentes. (A func¸a˜o de transic¸a˜o pode ser representada grafica-
mente.)
Resposta:
Loja = (Σ,Q, δ, q0, F ), onde
Σ = {p, e},
Q = {Pedido,Pagamento,Solicita,Prepara,Envio,Recebimento},
q0 = Pedido, F = {Recebimento}
δ = Pagamento
�
&&
// Pedido
p
88
p
&&
Prepara
� // Envio
e
**
Recebimento
Solicita
�
88
3
(b) (1 ponto) O comportamento da loja pode produzir uma situac¸a˜o indeseja´vel que e´ o da loja enviar
o(s) produto(s) de um pedido sem ter recebido por eles. Como esta situac¸a˜o fica representada no
autoˆmato finito?
Resposta:Existe um caminho a partir do estado Pedido que reconhece a palavra pe, represen-
tando que um pedido foi feito por um cliente e enviado pela loja, mas que na˜o inclui o estado
Pagamento.
3. (2 pontos) A linguagem Java permite a declarac¸a˜o de classes (que representam tipos de dados) atrave´s
da seguinte sintaxe:
c l a s s C {
. . .
}
onde C e´ um identificador que pode conter os caracteres alfanume´ricos, simplificadamente dados pelos
elementos do conjunto {0, 1, A,B,C}, a partir do seu segundo caracter. O primeiro deve ser alfabe´tico.
(a) (1 ponto) Descreva, graficamente, a func¸a˜o de transic¸a˜o de um autoˆmato finito que reconhec¸a o
le´xico de declarac¸o˜es de classe seguindo a sintaxe acima, isto e´, que aceite uma sequeˆncia de “pa-
lavras reservadas”, da sintaxe para declarac¸a˜o de classes, e identificadores.
Resposta:
// q0
� //
�
 
�
��
�
��
q1
c // q2
l // q3
a // q4
s // q5
s // q6
� // qf
�
��
p1
A,B,C // p2
0,1,A,B,C
vv
�
44
r1
{ // r2
�
77
t1
} // t2
�
::
(b) (1 ponto) Qual a limitac¸a˜o dos autoˆmato finitos do ponto de vista do processamento de declarac¸o˜es
sinta´ticas como esta? Em outras palavras, considerando-se a sintaxe dada, o que na˜o conseguem
reconhecer?
Resposta:
Autoˆmatos finitos determin´ısticos reconhecem linguagens regulares e sa˜o suficientes para a
especificac¸a˜o do le´xico de uma linguagem. A ana´lise sinta´tica, que identifica que palavras foram
declaradas na posic¸a˜o correta, necessita de linguagens livres de contexto, mais expressivas que
as linguagens regulares, e que sa˜o reconhecidas por autoˆmatos de pilha.
4

Outros materiais