Redes

Autômato Finito Não
Determinístico

Autômato Finito Não Determinístico
(AFN)
• Um AFN é uma quíntupla (Q, Σ, δ, I, F), onde:
– Q é um conjunto finito de um ou mais de estados;
– Σ é um alfabeto;
– I, um subconjunto de Q, é um conjunto não vazio de estados iniciais;
– F, um subconjunto de Q, é o conjunto de estados finais; – δ, a função de transição, é uma função total de Q x Σ para ℘(Q).

• Observe que um AFD é um caso particular de
AFN.

Exemplo AFN
• ({e1, e2}, {0,1}, δ, {e1}, {e2}), em que δ é δ e1

0
1
{e1, e2} {e1}

e2

∅

δ

Função de transição estendida
• Seja um AFN M=(Q, Σ, δ, I, F). A função de
ˆ
transição estendida δ , é uma função de ℘(Q) x Σ* para ℘(Q), definida recursivamente como: δˆ (φ , w) = φ

para todo w ∈ Σ*

δˆ ( A, ε ) = A

para todo A ⊆ Q δˆ ( A, ay ) = δˆ(∪ q∈A δ (q, a), y ) para todo A ⊆ Q , a ∈ Σ e y ∈ Σ*.

L( M ) = {w ∈ ∑ * | δˆ( I , w) ∩ F ≠ φ}

Exercícios
•

Construa AFNs para as seguintes linguagens: 1.
2.
3.
4.

{0,1}*{1010}, Σ= {0,1}
{0,00}{11}*, Σ= {0,1}
{a,b,c}*{abc}{a,b,c}*, Σ= {a,b,c}
{a,b,c}* {abc,bca} , Σ= {a,b,c}

AFN

AFD

Construção de subconjuntos de estados
Dado um AFN N = (Q, Σ, δ, I, F ), o AFD equivalente é
M(N ) = (Q’, Σ, δ’, q0’, F’ ) onde
–
–

–

O conjunto de estados de M é o conjunto potência de Q : Q’ =P (Q )={todos os subconjuntos de Q }
Cada estado de aceitação de M consiste de um subconjunto que contém um estado de aceitação.
I.e. F’ = {S ⊆ Q | S ∩F ≠ ∅ }
O estado inicial de M é o conjunto q0’ = I

a função δ’ é descrita a seguir:
6

AFN

AFD

Função de transição Delta.

Considere o exemplo
Antes de ler 1:

q2 q1 0
0,1

0,1
1

q0

0

1

0

Depois de ler 1:

0,1
0,1
1
1

0

Q: Porque δ’({q1,q2 },1) = {q2,q3 } ?
7

q3

AFN

AFD

Função de transição Delta.
De modo geral temos:

δ’ ( S , a ) = U δ(q, a ) = {q' ∈ Q ∃q ∈ S , q '∈ δ(q, a )} q∈S Isso completa a definição formal