Autômatos
Finitos Não
Determinístic
os (AFN)
Introdução
O não-determinismo é uma importante
generalização dos modelos de máquinas, sendo de
fundamental importância no estudo da teoria da
computação e da teoria das linguagens formais:
2
Funcionamento
A facilidade de não-determinismo para autômatos
finitos é interpretada como segue:
● A função programa, ao processar uma entrada
composta pelo estado corrente e símbolo lido, tem
como resultado um conjunto de novos estados
3
Computação Determinística Computação Não-Determinística
4
Definição Formal
Um autômato finito não-determinístico é uma 5-upla (, Q, ẟ , q0 , F),
onde:
• é um alfabeto finito.
• Q é um conjunto finito de estados.
• ẟ Q x → P(Q) é a função de transição.
• q0 Є Q é o estado inicial.
• F Q é o conjunto de estados de aceitação.
5
Exemplo 1
AFN para reconhecer palavras que contenham a subpalavra
aa ou bb, sobre o alfabeto {a, b}:
M = ({a, b}, {q0 , q1 , q2 , qf }, ẟ, q0 , {qf })
A função de transição (ẟ) pode ser representada
através de um grafo ou através de uma tabela:
6
7
O que é um autômato finito não
determinístico?
É um autômato finito que possui transições
vazias ou que para um símbolo de entrada de
um estado
Exercicio 1 fonte, existe mais de uma
transição
Projete possível.
um autômato finito não determinístico no
alfabeto {0,1} que aceite.
• Todas as palavras que têm pelo menos três 1s
• Todas as palavras que possuem um número ímpar de 1s
8
0 0 0,1
0 1 1
q1 q2 q3
1
q0
0 0
1
1
q4 q5
1 Probando as cadeias siguientes
010011 aceitada por q3 e q4
01010 não aceitada q3 e q4
011011 debe ser aceitada solo por q3
01000 debe ser aceitada solo por q4
Transiҫão vazia
10
Movimento vazio
11
Movimento vazio: como entender
12
Exemplo de um autðmato finito não-determinístico (AFN)
13
Formalizando o Autômatos
14
Autômato finito não determinístico
É uma automação na qual existem diversas rotas
diferentes para analisar um símbolo de entrada e são
classificadas em dois tipos.
1-Autômatos finitos não determinísticos com
transcisões de cordas vazias ɛ (AFN-ɛ )
2-Autômato finito não determinístico (AFN)
15
Exemplo de un (AFN-ɛ )
Seja o linguagem ser L={ w:w começa em a ou
termina em b} usando o alfabeto ∑={a,b}
A expresão regular e ER= a (ab)*| b
Cadeias começando com a
Cadeias que terminam en b
podem se unir para formar
16
17
Exemplo práctico da vida
q1
0,1 1
0
q0 1
q3
1
0
Σ = {0, 1}
q0= estado inicial neutro q2
q1= função de resfriamento de água
q2= função de aquecimento de água
q3 =estado final ou aceito (Epulsão da
água)
18
Exercicio-1
Projetar um AFN N2 sobre Σ = {a, b} que considere
L2 = {w | w possui aa ou bb como subpalavra}
tal que N2 = ({q0, q1, q2, qf }, Σ, δf , q0, {qf }).
a,b q1 a,b
a a
q0
qf
b
b
q2
19
Exercicio-2
Projetar um AFN N3 sobre Σ = {a, b} que considere
L2 = {w | w possui aaa como sufijo}
tal que N3 = ({q0, q1, q2, qf }, Σ, δf , q0, {qf }).
a,b
a a a
q0 q1 q2 qf
q3
a b
q0 {q0,q1 } q0
q1 q2 ∅
q2 qf ∅
*qf ∅
20
Exercicio-3
Determine a linguagem do AFN N4 abaixo:
Resposta: L(N4) = {a ∪ ab}
ER = a | ab
21
Exercicio-4
Determine a linguagem do AFN abaixo:
22
Exercicio-4
Seja AFND M = (Q, Σ, ẟ, q0,F), e F={q1, q3}
Construa o autômato e verifique se a string 0101 pertence
23
24