Automatos

FACENS - Faculdade de Engenharia de Sorocaba

T´picos em Computa¸ao I o c˜

Equivalˆncia entre AFD e AFN e
Autˆmato Finito N˜o-Determin´ o a ıstico (AFN) estado anterior
∗

Exemplo
L = {w | w ∈ (a |a+ b∗ ) } M = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 } F = {q0 , q1 } a,b q a a a símbolo lido conjunto de novos estados

δ

a

b {q1 }

q0 {q0 , q1 } q1 -

p1

p2

...

pn

A fun¸˜o programa, ao processar um entrada ca (estado corrente e s´ ımbolo lido), tem como resultado um conjunto de novos estados.

q0

a

q1

a

q2

a

q3

O n˜o determinismo ´ uma importante generaliza¸˜o dos a e ca modelos de m´quinas, sendo de fundamental importˆncia no esa a tudo da teoria da computa¸˜o e das linguagens formais. Qualquer ca AFN pode ser simulado por um AFD. Pode-se entender que o AFN assume simultaneamente todas as alternativas de estados poss´ ıveis {p0 , p1 , ..., pn } a partir do estado atual (q) e do s´ ımbolo lido (a).

• o ciclo em q0 realiza uma varredura pela entrada de s´ ımbolos a’s • o caminho q0 /q1 garante a ocorrˆncia de a antes da e ocorrˆncia de b’s e

AFN - Defini¸˜o ca
• M = (Σ, Q, δ, q0 , F ) – Σ – alfabeto de s´ ımbolos de entrada – Q – conj. de estados poss´ ıveis do autˆmato o o qual ´ finito e – δ – fun¸˜o de transi¸˜o ca ca – q0 – estado inicial (q0 ∈ Q) – F – conjunto dos estados finais tal que F est´ contido em Q a

Exerc´ ıcio
L = {w | w possui aaa como sufixo} M = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , qf } F = {qf }

δ

a

b

q0 {q0 , q1 } {q0 } q1 q2 qf {q2 } {qf } -

A linguagem aceita por um autˆmato finito n˜o-determin´ o a ıstico M = (Σ, Q, δ, q0 , F ) denotada por ACEITA(M), ou L(M) ´ o e conjunto de todas as palavras pertencentes a Σ∗ tais que existe pelo menos um caminho alternativo que aceita a palavra. Analogamente, REJEITA(M) ´ o conjunto de todas as e palavras pertencentes a Σ∗ rejeitadas por todos os caminhos alternativos de M (a partir de q0 ).

a,b

q0