LFA:
Unidade 03 – Parte B
Engenharia/Ciência da Computação
Prof. François
[email protected]
Equivalência entre AFN e AFD

Teorema: Equivalência entre AFD e AFN

A classe dos AFD é equivalente à classe dos AFN.


A prova consiste em mostrar que para todo AFN M
é possível construir um AFD M’ que realiza o
mesmo processamento, ou seja, M’ simula M.
A demonstração apresenta um algoritmo para
converter um AFN qualquer em um AFD
equivalente.
Equivalência entre AFN e AFD



A idéia central do algoritmo é a construção de
estados de M’ que simulem as diversas
combinações de estados de M.
A transformação contrária - construir um AFN a
partir de um AFD - não necessita ser
demonstrada, uma vez que decorre trivialmente
das definições (Por quê? Porque a função
programa  do AFN contém a função programa
’ do AFD).
Seja M = (, Q, , q0, F) um AFN qualquer e
seja M’ = (’, Q’, ’, <q0>, F’) um AFD
construído a partir de M como se segue:
Equivalência entre AFN e AFD




Q’ :Conjunto de todas as combinações, sem repetições, de
estados de Q, as quais são denotadas por <q1q2...qn>
onde qi  Q para i em {1, 2, ..., n}. Note-se que a ordem
dos elementos não identifica mais combinações. Por
exemplo: <quqv> = <qvqu>.
’ : Tal que ’(<q1...qn>, a) = <p1...pm> sss  ({q1, ...,
qn}, a) = {p1, ..., pm}, ou seja, um estado de M’ representa
uma imagem de todos os estados alternativos de M.
<q0>:Estado inicial.
F’ :Conjunto de todos os estados <q1q2...qn>  Q’ tal que
alguma componente qi  F, para i  {1, 2, ..., n}.
Equivalência entre AFN e AFD






PROVA:
A demonstração de que o AFD M’ simula o processamento
do AFN M é dada por indução sobre o tamanho da palavra.
Deve-se provar que, para uma palavra qualquer w de :
’(<q0>, w) = <q1...qu> sse ({q0}, w) = {q1, ..., qu}
(A prova está no livro, na página 58).
Exemplo: Construção de um AFD a partir de um
AFN.
Seja o AFN M6 = ({a,b}, {q0, q1, q2, qf}, 6, q0, {qf}),
dado no exemplo anterior e representado abaixo:
Equivalência entre AFN e AFD
Equivalência entre AFN e AFD

O AFD M6’ = ({a, b}, Q’, ’, <q0>, F’),
construído conforme o algoritmo dado é:
b
p0
b
a
b
p1
a
b
p2
a
pf
a
Equivalência entre AFN e AFD




onde:
Q’
=
{<q0>,<q1>,<q2>,<qf>,<q0q1>,<q0q2>,
...,<q0q1q2qf>}
F’ =
{<qf>,<q0qf>,<q1qf>,...,<q0q1q2qf>}
6’ = É tal conforme os valores dados na
tabela abaixo:
Equivalência entre AFN e AFD
6’
a
b
<q0>
<q0q1>
<q0>
<q0q1>
<q0q1q2>
<q0>
<q0q1q2>
<q0q1q2qf>
<q0>
<q0q1q2qf>
<q0q1q2qf>
<q0>
Equivalência entre AFN e AFD

No grafo que representa M6’, acima, p0,
p1, p2 e pf denotam respectivamente
<q0>, <q0q1>, <q0q1q2>,
<q0q1q2qf>.
AF com Movimento vazio





Autômato Finito com Movimento Vazio
Movimentos vazios constituem uma generalização dos AFN e
são transições que ocorrem sem que haja a leitura de
símbolo algum
Os movimentos vazios podem ser interpretados como um
não-determinismo interno do autômato, que é encapsulado.
A não ser por uma eventual mudança de estados, nada mais
pode ser observado sobre um movimento vazio..
Qualquer AF pode ser simulado por um autômato finito
não-determinístico
AF com Movimento vazio




Definição: Autômato Finito com
Movimento Vazio (AF)
Um autômato finito não-determinístico e
com movimento vazio (AFN), ou
simplesmente autômato finito com
movimento vazio (AF), é uma quíntupla:
M = (, Q, , q0, F),
onde:
AF com Movimento vazio






Alfabeto de símbolos de entrada
QConjunto finito de estados possíveis do
autômato
 Função programa ou função de transição
: Q x (  {})  2Q, parcial.
q0 Estado inicial tal que q0  Q
F Conjunto de estados finais, tais que F 
Q.
Portanto os componentes do AF são os mesmos
do AFN, com exceção da função programa (ver
figura abaixo).
AF com Movimento vazio

q
an
p1
...
a1
p0
pn
AF com Movimento vazio



O processamento dos AF é similar ao dos AFN. Por
analogia o processamento de uma transição para uma
entrada vazia também é não-determinística. Assim um
AF ao processar uma entrada vazia assume
simultaneamente os estados de origem e destino da
transição.
Exemplo: Autômato Finito com Movimento Vazio
O AF M7 = ({a,b}, {q0, qf}, 7, q0, {qf}), representado
na figura abaixo reconhece a linguagem L7 ={ w |
qualquer símbolo a antecede qualquer símbolo b }, onde
7 é representada na forma da tabela:
AF com Movimento vazio
7
a
b

q0
{q0}
-
{qf}
qf
-
{qf}
-
AF com Movimento vazio
Computação Vazia





Seja M = (, Q, , q0, F) um autômato finito com
movimentos vazios.
a) A Computação Vazia ou Função Fecho Vazio, a
partir de um estado, denotada por:  : Q  2Q ,
e é indutivamente definida como segue:
 (q) ={q}, se (q, ) é indefinida;
 (q) ={q} U (q, ) U (Up(p)), caso contrário;
b) a Computação Vazia ou Função Fecho Vazio, a
partir de um conjunto de estados finito, denotada
por:
Computação Vazia








* : 2Q  2Q
é tal que
* (P) = Uqp (q)
Lembrar que * e  são agrupadas em .
Considere o autômato finito com movimentos
vazios do exemplo anterior.
Então:  (q0) = {q0, qf }
 (qf ) = {qf }
({q0,qf ) = {q0, qf }
Computação Vazia

A computação de um autômato finito com
movimentos vazios, para uma palavra de entrada
w, consiste na sucessiva aplicação da função
programa para cada símbolo de w (da esquerda
para a direita), cada passo de aplicação intercalado
com computações vazias, até ocorrer uma condição
de parada. Assim, para cada conjunto de estados
alternativos assumido pelo autômato, antes de
processar a próxima transição, é necessário
determinar todos os demais estados atingíveis
exclusivamente por movimentos vazios.
Computação Vazia





Definição - Função Programa Estendida,
Computação
Seja M = (, Q, , q0, F) um autômato finito com
movimentos vazios. A Função Programa Estendida
ou Computação de M, denotada por:
* : 2Q x *  2Q
é a função programa:  : Q x ( U {})  2Q
estendida para um conjunto finito de estados e
para uma palavra e é indutivamente definida como
segue:
Computação Vazia





*(P, ) =  (P)
*(P,wa) =  (R) onde R={r|r  (s,a) e s 
*(P,w)}
A parada do processamento, a linguagem
aceita e a rejeitada é igual à do AFN
ACEITA(M)={w | *({qo}, w) ∩ F ≠Ф}
REJEITA(M)={w | *({qo}, w) ∩ F = Ф ou
*({qo}, w) é indefinida}
Computação Vazia



Exemplo de Computação Vazia
Considere a seguinte linguagem sobre o
alfabeto { a, b, c}, La = {w | w possui como
sufIxo a ou bb ou ccc}
O autômato finito com movimentos vazios:
Computação Vazia





O autômato descrito acima M8 = ({ a, b, c},
{q0, q1, q2, q3, q4, q5, q6, qf}, 8, q0,
{qf})
é tal que ACEITA(M8) = L8
E em relação à computação vazia, vale que,
por exemplo:,
 ({q0}) = {q0, q1, q2, q4}
E a computação da entrada abb é:
Computação Vazia







*({qo},abb) =  ({r |r  (s,b) e s 
*({q0},ab)}) (1)
Sendo que
*({qo},ab) =  ({r |r  (s,b) e s  *({q0},a)})
(2)
E
*({qo},a) =  ({r |r  (s,a) e s  *({q0}, )})
(3)
Como
*({qo}, ) =  ({q0})={q0, q1, q2, q4}
Computação Vazia






O qual considerado em (3):
*({qo},a) = })={q0, q1, q2, q4,qf}
O qual considerado em (2):
*({qo},ab) = })={q0, q1, q2, q3,q4}
O qual considerado em (1):
*({qo},abb) = })={q0, q1, q2, q3, q4, qf}
Computação Vazia




Equivalência entre AFN e AFN
Seja M = (, Q, , q0, F) um AFN. E MN = (, Q,
, q0, FN ) um autômato construído a partir de M
como segue:
a) N : Q x   2Q é tq N (q,a) = * ({q},a)
b) FN é o conjunto de todos os estados q
pertencentes a Q tq:  (q) ∩ F ≠Ф (todos os
estados que atingem estados finais via
computações vazias).
Computação Vazia


EXEMPLO - Construção de AFN a partir de AFN
Considere o autômato finito com movimentos
vazios M9 na figura abaixo::
Computação Vazia

E 9 dado por
9
a
b

q0
{q0}
-
{q1}
q1
-
q2
{q2}
{q1} {q2}
-
-
Computação Vazia

Assim o automato M9 = ({a, b}, {q0, q1, q2}, 9,

E o correspondente AFN:





qo, {q2})
M9N = ({a, b}, {q0, q1, q2}, 9N, qo, FN) é
construído assim:
FN = {q0, q1, q2, pois:
 (q0) = {q0, q1, q2}
 (q1) = {q1, q2}
 (q2) = {q2}
Computação Vazia






Na construção de 9N note-se que:
9*({q0}, ))={q0, q1, q2}
9*({q1}, ))={q1, q2}
9*({q2}, ))={q2}
Assim, 9N é tq:
9N (q0,a)= 9*({q0},a)=  ({r |r  (s,a) e
s  *({q0}, )})= {q0, q1, q2}
Computação Vazia




9N (q0,b)= 9*({q0},b)=  ({r |r  (s,b) e
s  *({q0}, )})= {q1, q2}
9N (q1,a)= 9*({q1},a)=  ({r |r  (s,a) e
s  *({q1}, )})= {q2}
9N (q1,b)= 9*({q1},b)=  ({r |r  (s,b) e
s  *({q1}, )})= {q1, q2}
9N (q2,a)= 9*({q2},a)=  ({r |r  (s,a) e
s  *({q2}, )})= {q2}
Computação Vazia


9N (q2,b)= 9*({q2},b)=  ({r |r  (s,b) e
s  *({q2}, )}) é indefinida
E o AFN equivalente é: