Automatos Finitos
Renato E. N. Moraes
Universidade Federal do Esprito Santo
Abril 2015
Renato E. N. Moraes, UFES Automatos Finitos 1/31
Conteudo
Automato finito
Automato finito determinstico
Linguagem de automato finito determinstico
Automato finito Nao Determinstico
Renato E. N. Moraes, UFES Automatos Finitos 2/31
Conteudo
Automato finito
Automato finito determinstico
Linguagem de automato finito determinstico
Automato finito Nao Determinstico
Renato E. N. Moraes, UFES Automatos Finitos 3/31
Automato finito
Definicao
Automato finito e um procedimento (ou maquina) que so pode conteruma quantidade finita e limitada de informacao a qualquer momento.Essa informacao e representada por um estado da maquina, e so existeum numero finito de estados.
I Um procedimento e uma sequencia finita de instrucoes claramentedescritas, que podem ser executadas mecanicamente em tempofinito.I mecanicamente: nao ha duvidas sobre o que ser feitoI em tempo finito: nao ha duvidas de que a instrucao pode ser levada
ate sua conclusao
Renato E. N. Moraes, UFES Automatos Finitos 4/31
Conteudo
Automato finito
Automato finito determinstico
Linguagem de automato finito determinstico
Automato finito Nao Determinstico
Renato E. N. Moraes, UFES Automatos Finitos 5/31
Automato finito determinstico
Definicao
Um Automato finito determinstico M, sobre um alfabeto e umsistema (K ,, , i ,F ), onde
K e um conjunto de estados finito, nao vazio; e um alfabeto de entrada (finito) : K K e a funcao de transicaoi K e o estado inicialF K e o conjunto de estados finais.
I Diz-se determinstico pois:I e uma funcao que determina o proximo estado a ser assumido
quando a maquina M se encontra no estado q e le da entrada osmbolo a: o estado (q, a)
Renato E. N. Moraes, UFES Automatos Finitos 6/31
Automato finito determinstico
Definicao
Um Automato finito determinstico M, sobre um alfabeto e umsistema (K ,, , i ,F ), onde
K e um conjunto de estados finito, nao vazio; e um alfabeto de entrada (finito) : K K e a funcao de transicaoi K e o estado inicialF K e o conjunto de estados finais.
I Diz-se determinstico pois:I e uma funcao que determina o proximo estado a ser assumido
quando a maquina M se encontra no estado q e le da entrada osmbolo a: o estado (q, a)
Renato E. N. Moraes, UFES Automatos Finitos 6/31
Automato finito determinstico
I Informalmente, um automato finito determinstico:1. parte de um estado inicial de uma cadeia2. muda de estado de acordo com a funcao de transicao3. atinge um estado final ao terminar de ler a cadeia
Renato E. N. Moraes, UFES Automatos Finitos 7/31
Automato finito determinstico
I Uma das maneiras de visualizar o funcionamento de um automatofinito determinstico e atraves de um controle finito que le smbolosde uma fita de entrada (onde se encontra a cadeia de entrada),sequencialmente, da esquerda para a direita.
a b a b a a a
ControleFinitoestadoq
Renato E. N. Moraes, UFES Automatos Finitos 8/31
Exemplo
I Considere o automato finito determinstico M = (K ,, , i ,F ), ondetemosI K = {q0, q1, q2, q3}I = {a, b}I i = q0I F = {q3}
I onde a funcao de transicao e dada pela tabela abaixo : {q0, q1, q2, q3} {a, b} {q0, q1, q2, q3}
a bq0 q1 q2q1 q0 q3q2 q3 q0q3 q2 q1
Renato E. N. Moraes, UFES Automatos Finitos 9/31
Exemplo
I Podemos representar o automato finito determinstico M por umdiagrama de transicoes, ou diagrama de estados.
a b
q0 q1 q2q1 q0 q3q2 q3 q0q3 q2 q1
q0 q1
q2 q3
a
a
a
a
b b b b
Renato E. N. Moraes, UFES Automatos Finitos 10/31
Exemplo
I Cada estado de um autonomo finito corresponde a uma informacaosobre a parte da cadeia de entrada ja lida
I Para o exemplo, podemos dizer: se o estado atingido e q2, entao1. o numero de smbolos a ja lidos e par, e2. o numero de smbolos b ja lidos e mpar
I Em resumo, temos:
quantidade de a quantidade de b
q0 par parq1 mpar parq2 par mparq3 mpar mpar
Renato E. N. Moraes, UFES Automatos Finitos 11/31
Conteudo
Automato finito
Automato finito determinstico
Linguagem de automato finito determinstico
Automato finito Nao Determinstico
Renato E. N. Moraes, UFES Automatos Finitos 12/31
Linguagem de automato finito determinstico
quantidade a bq0 par parq1 mpar parq2 par mparq3 mpar mpar
q0 q1
q2 q3
a
a
a
a
b b b b
I A linguagem aceita ou reconhecida por M e a linguagem formadapelas cadeias em que a quantidade de a e de b sao ambos mpares.
I Isso se deve ao fato de que o unico estado final e q3I Por exemplo:
I a cadeia abaa e da linguagem de MI com essa cadeia, os seguintes estados sao atingidos:
I q0 q1 q3 q2 q3I Como o ultimo estado e final, a cadeia e aceita.
Renato E. N. Moraes, UFES Automatos Finitos 13/31
Linguagem de automato finito determinstico
I Formalmente:I configuracao de M: par composto pelo estado corrente e pela
cadeia de entrada x que ainda nao foi lida, (q, x) K I a configuracao (i , x) e a configuracao inicial de M para a cadeia xI qualquer configuracao (q, ) e uma configuracao final se q FI A mudanca de configuracao e caracterizada pela relacao `, definida
como: (q, ax) ` (p, x) se e somente se (q, a) = p
I Podemos definir a linguagem L(M) por:
L(M) = {x |(i , x) ` (f , ), com f F}
Renato E. N. Moraes, UFES Automatos Finitos 14/31
Exemplo
quantidade a bq0 par parq1 mpar parq2 par mparq3 mpar mpar
q0 q1
q2 q3
a
a
a
a
b b b b
I Para mostrar que abaa L(M), basta observar que(q0, abaa) ` (q1, baa) ` (q3, aa) ` (q2, a) ` (q3, )
I Para mostrar que abab / L(M), basta observar que(q0, abab) ` (q1, bab) ` (q3, ab) ` (q2, b) ` (q0, ),
I Assim, M aceita a linguagem
L(M) = {x {a, b}| os numeros de a e de b em x sao mpares}Renato E. N. Moraes, UFES Automatos Finitos 15/31
Linguagem de automato finito determinstico
I Uma caracterizacao alternativa de L(M) pode ser baseada em umaextensao da funcao , feita de forma a aceitar cadeias no segundoargumentoI domnio K , em vez de K I Pode-se definir a nova funcao : K K por
(q, ) = q, q K(q, ax) = ((q, a), x), q K ,x ,a
I Para mostrar que abaa L(M), basta observar que(q0, abaa) = (q1, baa) = (q3, aa) = (q2, a) = (q3, ) = q3 F
Renato E. N. Moraes, UFES Automatos Finitos 16/31
Conteudo
Automato finito
Automato finito determinstico
Linguagem de automato finito determinstico
Automato finito Nao Determinstico
Renato E. N. Moraes, UFES Automatos Finitos 17/31
Automato finito nao determinstico
I Em oposicao ao que acontece com o afd, a funcao de transicao deum afnd nao precisa determinar exatamente qual deve ser o proximoestado.
I A funcao de transicao fornece uma lista (um conjunto) de estadospara os quais a transicao poderia ser feita.
I Essa lista pode ser vazia, ou ter um numero qualquer positivo deelementos.
Renato E. N. Moraes, UFES Automatos Finitos 18/31
Automato finito nao determinstico
I A possibilidade de escolha entre varios caminhos a serem seguidosnos leva a modificar a definicao de aceitacao.I Um afd aceita se o ultimo estado atingido e final;I um afnd aceita se existe uma sequencia de escolhas tal que o ultimo
estado atingido e final.
I Pode-se alternativamente imaginar que o afnd escolhe, adivinha, ocaminho certo para a aceitacao, uma vez que a existencia deescolhas erradas, que nao levam a um estado final, e irrelevante.
Renato E. N. Moraes, UFES Automatos Finitos 19/31
Exemplo
I Considere o afnd dado pelo diagrama abaixo e a cadeia de entradaababa.
Renato E. N. Moraes, UFES Automatos Finitos 20/31
Exemplo
I A cadeia ababa e aceita, porque uma das possibilidades e asequencia de estados q0, q1, q1, q1, q1, q2.
I Naturalmente, com a mesma cadeia, poderamos escolher asequencia q0, q1, q1, q1, q1, q1 que nao leva a um estado final.
I Ou a sequencia q0, q1, q1, q2 interrompida, porque q2 nao preveuma transicao com o segundo b.
I Nos casos em que o automato adivinhou errado nao criamproblemas para a aceitacao, porque existe um caminho certo.
Renato E. N. Moraes, UFES Automatos Finitos 21/31
Exemplo
I Este afnd aceita a linguagem das cadeias de comprimento maior ouigual a 2, cujo primeiro e ultimo smbolos sao a, sendo os restantesquaisquer.
I Exerccio: Crie um afd que aceita a mesma linguagem e comparecom este afnd.
Renato E. N. Moraes, UFES Automatos Finitos 22/31
Automato finito nao determinstico
Definicao
Formalmente, um Automato finito nao determinstico (afnd) M,sobre um alfabeto e um sistema (K ,, , i ,F ), onde
K e um conjunto finito, nao vazio de estados; e um alfabeto de entrada (finito) : K ( {}) P(K ) e a funcao de transicaoi K e o estado inicialF K e o conjunto de estados finais.
I A notacao P(K ) indica o conjunto partes de K (conjunto potenciade K , ou, ainda, powerset de K ), o conjunto de todos ossubconjuntos de K .
Renato E. N. Moraes, UFES Automatos Finitos 23/31
Automato finito nao determinstico
Definicao
Formalmente, um Automato finito nao determinstico (afnd) M,sobre um alfabeto e um sistema (K ,, , i ,F ), onde
K e um conjunto finito, nao vazio de estados; e um alfabeto de entrada (finito) : K ( {}) P(K ) e a funcao de transicaoi K e o estado inicialF K e o conjunto de estados finais.
I Pela definicao e uma funcao que aceita como argumentos q e aonde:I q e um estado e a pode ser um smbolo de ou a cadeia vazia .
I Em qualquer caso, (q, a) e sempre um conjunto de estados, ou seja,um subconjunto de K .
Renato E. N. Moraes, UFES Automatos Finitos 24/31
Automato finito nao determinstico
I Se tivermos (q, a) = p1, p2, . . . , pk , entendemos que o automatoM, a partir do estado q, pode escolher um dos estados p1, p2, . . . , pkpara ser o proximo estado.
I Se a = , nenhum smbolo da entrada e lido;I se a 6= , o smbolo a da entrada e lido.I Podemos considerar o caso a = como correspondendo a transicoes
espontaneas: M muda de estado sem estmulo da entrada.
I Se tivermos (q, a) = , nao ha transicoes possveis a partir doestado q com o smbolo a.
Renato E. N. Moraes, UFES Automatos Finitos 25/31
Linguagem de automato finito nao determinstico
I Definimos configuracoes para o caso do afnd da mesma forma queanteriormente.I A mudanca de configuracao e caracterizada pela relacao `, definida
como:(q, ax) ` (p, x) se e somente se p (q, a)
I Note que a pode ser a cadeia vazia, caso em que temos
(q, x) ` (p, x) se e somente se p (q, )
I Podemos definir a linguagem L(M) por:
L(M) = {x |(i , x) ` (f , ), com f F}
Renato E. N. Moraes, UFES Automatos Finitos 26/31
Exemplo (continuacao)
I Temos, para a mesma cadeia ababa de entrada,
(q0, ababa) ` (q1, baba) ` (q1, aba) ` (q1, ba) ` (q1, a) ` (q3, )
I e, portanto, ababa L(M).I Temos tambem o caminho errado
(q0, ababa) ` (q1, baba) ` (q1, aba) ` (q1, ba) ` (q1, a) ` (q1, )
I que leva a` configuracao nao final (q1, ), e nao permite nenhumaconclusao.
Renato E. N. Moraes, UFES Automatos Finitos 27/31
Exemplo (continuacao)
I Cadeias como bab e abab nao levam a configuracoes finais e nao saoaceitas.
I Da configuracao (q0, bab) nenhuma configuracao e atingvel;I para abab temos:
(q0, abab) ` (q1, bab) ` (q1, ab) ` (q1, b) ` (q1, )
I Adicionalmente, temos um outro caminho
(q0, abab) ` (q1, bab) ` (q1, ab) ` (q2, b)
Renato E. N. Moraes, UFES Automatos Finitos 28/31
ExemploI Considere o afnd dado pelo diagrama abaixo.
I M aceita cadeias da forma cyc, onde c pode ser a ou b e y pode serqualquer cadeia de as e bs.
Renato E. N. Moraes, UFES Automatos Finitos 29/31
ExemploI A cadeia ababa = c y c = a bab a e aceita por M, atraves da
sequencia de configuracoes abaixo,I a primeira e a ultima transicoes sao realizadas atraves de
transicoes-.
(A, ababa) M le e adivinha que c = a` (B, ababa) M le a e confere que c = a` (C , baba) M le b` (C , aba) M le a e adivinha que este a faz parte de y` (C , ba) M le b` (C , a) M le a e adivinha que este a e o ultimo c` (D, ) M le e adivinha que a cadeia acabou` (I , ) M aceita
Renato E. N. Moraes, UFES Automatos Finitos 30/31
ExemploI Todas as configuracoes atingveis (caminhos certos e errados) estao
indicadas abaixo:
(A, ababa)` (B, ababa) ` (C , baba) ` (C , aba) ` (C , ba) ` (C , a) ` (C , ) nao aceita ` (D, ) ` (I , ) Ok! aceita ` (D, ba) ` (I , a) bloqueado` (F , ababa) bloqueado
Renato E. N. Moraes, UFES Automatos Finitos 31/31
Main PartAutmato finitoAutmato finito determinsticoLinguagem de autmato finito determinsticoAutmato finito No Determinstico
Top Related