Buscar

vs 2013.2

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

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

Outros materiais