Baixe o app para aproveitar ainda mais
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
Compartilhar