Upload
italomeshihim
View
216
Download
0
Embed Size (px)
DESCRIPTION
automato finito determinístico
Citation preview
BCC242 Aumato Finito Determinstico
Mquinas de Estados Finitos As mquinas de estados finitos so mquinas
abstratas que capturam partes essenciais de algumas mquinas concretas.
Tipos Tradutores mquinas com entradas e sada Reconhecedores possuem duas sadas possveis,
aceita e rejeita. A memria de uma mquina de estados finitos
limitada e organizada em torno do conceito de estado.
Exemplo 1 Um homem, um leo, um coelho e um repolho
devem atravessar um rio usando uma canoa, com a restrio de que o homem deve transportar no mximo um dos trs de cada vez de uma margem a outra. Alm disso, o leo no pode ficar na mesma margem que o coelho sem a presena do homem, e o coelho no pode ficar com o repolho sem a presena do homem. O problema consiste em determinar se possvel fazer a travessia.
Exemplo 2 Projetar uma mquina que, dada uma
seqncia de 0s e 1s, determinar se o nmero representado por ela na base 2 divisvel por 6.
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
Mais parecido com computer:
01
esta seta denotainicio
crculoduplodenotaaceita
entradaem fitalida daesquerdap/ direita
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
Autmato Finito Determinstico
0
1
0
1
1 1 0 0 1
01
REJEITA!
Autmato Finito Determinstico
0
1
0
1
01
Q: Que tipos de bitstringsso aceitos?
Autmato Finito Determinstico
0
1
0
1
01
R: Bitstrings que representamnmeros binrios pares.
Autmato Finito DeterminsticoExercicio: Projete uma mquina que
determina quando um string de entrada um nmero na base-10 divisvel por 3
Qual deve ser o alfabeto?Como voc pode determinar se um nmero
divisvel por 3?
Autmato Finito DeterminsticoSoluo:
0 mod 3
1 mod 3
2 mod 30,3,6,9
0,3,6,9
0,3,6,9
1,4,7
1,4,7
1,4,7
2,5,8 2,5,8
2,5,8
Definio Formal de FA
DEF: Um autmato finito (determinstico)(FA) consiste de um conjunto de estados Q, um alfabeto , transiesrotuladas entre estados , um estadoinicial q0 Q, e um conjunto de estadosde aceitao F.
M = (Q, , , q0, F )
Definio Formal de FANote que o string de entrada, assim como a
fita que contm o string de entrada, soimplcitos na definio de um FA. Ouseja, a definio prov apenas uma visoesttica. necessria explicaoadicional para entender como um FA interage com a sua entrada.
Porque Determinstico?Determinstico significa que existe
informao suficiente para sempredeterminar qual o prximo estado para o qual vai o Autmato, ao ler um dado smbolo. Nosso Exemplo de Mquina de Venda de fato no era determinsticoporque, depois de terem sido depositados$.45, os efeitos de depsitos adicionaisso indefinidos.
0 mod 3 1 mod 3
2 mod 3
0,3,6,9
0,3,6,9
0,3,6,9
1,4,7
1,4,71,4,7
2,5,8 2,5,8
2,5,8
Exercicio: Obtenha adescrio formal desteautmato.
Definio de FA, exemploQ = { 0 mod 3, 1 mod 3, 2 mod 3 } (
renomeie: {q0, q1, q2} ) = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }q0 = 0 mod 3F = { 0 mod 3 } requer explicao adicional
A funo de transio Determina o estado para o qual vai o
autmato, dado o estado corrente e o smbolo corrente na entrada. I.e., dado um estado q Q e um smbolo a , define um nico estado alvo q Q. Emoutras palavras, uma funo do produto Cartesiano Q x em Q :
QQ :
A funo de transio
?),(:Questo
.)5,(,)3,( ,)7,( ,)2,(,)9,( ,)2,(
:
122221
010020
=
===
===
jq
qqqqqqqqqqqq
i
A funo de transio
3 mod )(),( jii qjq +=Usualmente a funo de transio notem uma definio tal como nesse caso,dada por uma frmula simples.
Definio Formal de FA:Dinmica
Como um FA opera sobre um string? Existe implicitamente a noo de umafita auxiliar que contm o string. O FA la fita da esquerda para a direita e cadacaractere faz com que o autmato vpara um novo estado, definido pelafuno . Quando o string lido completamente, ele aceito ou no, conforme o estado final do FA seja ouno um estado de aceitao.
Definio Formal de FA:Dinmica
DEF: Um string u aceito por um autmato sse o caminho a partir do estado inicial q0 que rotulado por u termina em um estado de aceitao.
Linguagem Aceita por um FADEF: A linguagem aceita por um FA M o
conjunto de todos os strings que so aceitospor M e denotada por L (M ).
Intuitivamente, pense em todos os possveiscaminhos que levam do estado inicial a um estado de aceitao do autmato. Ento penseem todas as possveis maneiras de rotularesses caminhos (caso existam mltiplos rtulosem algumas setas).
Linguagens RegularesVeremos mais adiante que nem toda
linguagem pode ser descrita como umalinguagem aceita por um FA. Umalinguagem que aceita por algum FA exibe um alto grau de regularidade.
DEF: Uma linguagem L chamadalinguagem regular se existe um FA M talqueL = L (M ).
Funo de transio estendida Seja um AFD M=(Q, , , q0, F). A funo de
transio estendida , uma funo de Q x * para Q, definida recursivamente como:
para todo a e y *.
)),,((),(),(
yaeayq
=
=
}),(|*{)( 0 FwqwML =
Algumas propriedades Sejam os AFDs M1=(Q1, , 1, i1, F1) e M2
=(Q2, , 2, i2, F2). Existem AFDs para as seguintes linguagens.
(1) Pode ser obtido a partir de M1simplesmente colocando-se como estados finais aqueles que no so finais em M1.
)()()3()()()2(
)()1(
21
21
1
MLMLMLML
ML
Algumas propriedades (2) Seja o AFD M3= (Q1xQ2, , 3, [i1,i2],
F3), construdo com 3([e1,e2],a) = [1(e1, a), 2(e2, a)] F3 = F1 x F2
(3) Seja o AFD M3= (Q1xQ2, , 3, [i1,i2], F3), construdo com 3([e1,e2],a) = [1(e1, a), 2(e2, a)] F3 = {[e1,e2] Q1xQ2 | e1 F1 ou e2 F2}
ExerccioDefina um AFD que aceita a linguagem L
sobre o alfabeto {0,1} cujos strings possuem tamanho mltiplo de 3 outerminam com 1.
Defina um AFD que aceita a linguagem L sobre o alfabeto {0,1} cujos strings comeam com 0 e terminam com 10 oucom 11