Baixe o app para aproveitar ainda mais
Prévia do material em texto
VS — Linguagens Formais e Teoria da Computac¸a˜o, 2013.2 Prof. Christiano Braga Instituto de Computac¸a˜o Universidade Federal Fluminense 20/12/2013 Gabarito 1. (a) (1 ponto) Mostre que a linguagem L = a(a+ b)2 e´ regular. (b) (1 ponto) A linguagem ¬L e´ regular? Em caso positivo, apresente seu autoˆmato. Caso contra´rio, apresente uma demons- trac¸a˜o utilizando o lema do bombeamento. Resposta: (a) Pela aplicac¸a˜o do mapeamento de expresso˜es regulares a` autoˆmatos finitos com transic¸o˜es ǫ: GFED@ABCq00 a // GFED@ABCqf 0 ǫ !!❈ ❈❈ ❈❈ ❈❈ ❈❈ GFED@ABCq03 a // GFED@ABCqf 3 ǫ !!❈ ❈❈ ❈❈ ❈❈ ❈❈ // GFED@ABCq06 a // GFED@ABCq02 ǫ ==④④④④④④④④④ ǫ !!❈ ❈❈ ❈❈ ❈❈ ❈❈ GFED@ABCqf 2 ǫ // GFED@ABCq05 ǫ ==④④④④④④④④④ ǫ !!❈ ❈❈ ❈❈ ❈❈ ❈❈ ?> =<89 :;76 5401 23qf 5 GFED@ABCq01 b // GFED@ABCqf 1 ǫ ==④④④④④④④④④ GFED@ABCq04 b // GFED@ABCqf 4 ǫ ==④④④④④④④④④ (b) Sim. Linguagens regulares sa˜o fechadas para a operac¸a˜o de complemento. 2. (a) (1 ponto) Qual e´ o tipo de autoˆmato finito da Figura 1? (b) (1 ponto) Que linguagem e´ reconhecida por ele? (c) (1 ponto) Qual e´ o AFD associado a ele? // ?>=<89:;q0 ǫ // a 55 ?>=<89:;q1 b 55 ǫ //?> =<89 :;/. -,() *+q2 a 55 Figura 1. Autoˆmato finito para a Questa˜o 2 Resposta: (a) AFNǫ (b) a ∗b∗a∗. (c) AFN //?> =<89 :;76 5401 23q0 a,b %% a 55 a,b //?> =<89 :;76 5401 23q1 b 55 a,b //?> =<89 :;76 5401 23q2 a 55 AFD //GF ED@A BC?> =<89 :;{q0} a // b $$■ ■■ ■■ ■■ ■■ GF ED@A BC?> =<89 :;{q0, q1, q2} a �� b ��GF ED@A BC?> =<89 :;{q1, q2} b WW a //GF ED@A BC?> =<89 :;{q2} a GG 3. (1 ponto) Mostre que a linguagem L = {anbn | n ≥ 0} e´ livre de contexto. Resposta: ?>=<89:;q0 (a,ǫ,B) )) (b,B,ǫ) // (?,?,ǫ) ❆ ❆❆ ❆❆ ❆❆ ❆ ?>=<89:;q1 (?,?,ǫ)~~⑥⑥ ⑥⑥ ⑥⑥ ⑥⑥ (b,B,ǫ) uu ?> =<89 :;76 5401 23qf 4. (2 pontos) Mostre a ma´quina de Turing que leˆ da fita um nu´mero em bina´rio e escreve seu sucessor na fita. Resposta: // ?>=<89:;q0 (1,1,D),(0,0,D) 55 (β,β,E)// ?>=<89:;q1 (1,0,E) 55 (β, 1, D), (0, 1, E) // ?>=<89:;q2 (0,0,D),(1,1,D) ii (β,β,E)//?> =<89 :;76 5401 23qf 5. (a) (1 ponto) Formule o “problema da parada” como uma linguagem. (b) (1 ponto) Qual a relac¸a˜o entre este problema e computabilidade? Resposta: (a) H = {(i, x) | o programa i para quando executado com a entrada x.} (b) A tese de Church-Turing enuncia que os problemas computa´veis sa˜o aqueles decid´ıveis por uma ma´quina de Turing. O chamado “problema da parada” e´ um exemplo de um problema para o qual na˜o existe uma ma´quina de Turing que o decida. 2
Compartilhar