Linguagens Formais e Aut matos Aula 4 Aut matos Finitos AFND 06.09.2016

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos Finitos Não Determinísticos
• O não determinismo é uma importante
generalização dos modelos de máquinas, sendo
de fundamental importância no estudo dos
modelos para concorrência, da teoria da
computação e das linguagens formais, entre
outros.
• Os autômatos finitos podem ser estendidos
para incluir não-determinismo, isto é, para
permitir que vários caminhos sejam
percorridos simultaneamente.
p
q2
a
Estado
Anterior
Símbolo
Lido
Conjunto
de Novos
Estados
q1 qn
a a
...
• Assim, para um Autômato Finito Não
Determinístico (AFND) visto como uma
máquina composta por fita, unidade de
controle e programa, assume um conjunto de
estados alternativos.
• É como se houvesse uma multiplicação da
unidade de controle, uma para cada alternativa,
processando independentemente, sem
compartilhar recursos com as demais.
• Desta forma, o processamento de um
caminho não influi no estado, símbolo lido e
posição da cabeça dos demais caminhos
alternativos e todos os caminhos alternativos
são investigados simultaneamente.
Nos AFD:
• As Transições são bem definidas.
• A função de transição leva a um único estado.
• A sequência de estados é única para cada
palavra.
Nos AFND:
• As transições são ambíguas.
• A função de transição pode levar a vários
estados alternativos.
• Várias sequências possíveis de estados.
Nos AFND:
• O próximo estado, não necessariamente, é
unicamente determinado pelo estado atual e
pelo símbolo de entrada.
• Podemos ter zero, uma ou mais transições de
estado com o mesmo símbolo de entrada.
Exemplo: Observe o AFND a seguir:
q0 q2
0,1
q1
1 0
 0 1
q0
q1
{q0,q1}q0
q2
q2  

Exemplo: Considere a entrada 110:
q0 q2
0,1
q1
1 0
1
q0
q0 q1
q0 q1
1
parou
1
1 1
q0
0
q2
0
 Estado
Final
Como se chegou a q2 por pelo
menos um caminho, então a
palavra 110 é aceita pelo AFND.
Árvore de Parsing
Definição 17: Um Autômato Finito Não
Determinístico (AFND) é uma 5-upla
M=(K,Σ,,s,F) onde:
• K (ou Q), Σ, s e F são definidos como no AFD.
•  (ou ) é uma relação (denominada relação de
transição) sobre K×Σ.
• Em um AFND uma palavra w é aceita se, e
somente se, existe ao menos uma evolução (s,
w) ⊦ *M (f, λ) com f ∈ F.
• Assim como para um AFD, um Autômato
Finito Não Determinístico (AFND) evolui de
um estado para outro.
• Assim, para um estado p e um símbolo a:
δ(p, a) = {q’, q”, q’’’,...}.
é uma transição do autômato.
Parada do processamento de um AFD
A parada do processamento de um Autômato
Finito Não Determinístico para a entrada w pode
ser de duas maneiras.
• Aceita a entrada w. Após processar o último
símbolo da fita, existe pelo menos um estado
final pertencente ao conjunto de estados
alternativos atingidos.
Parada do processamento de um AFD
• Rejeita a entrada w:
 Se, após processar o último símbolo da fita,
todos os estados alternativos atingidos são não
finais.
 Ou, em algum momento, ao longo do
processamento de w, a função
programa é indefinida para o
argumento (estado corrente e símbolo
lido da fita) e o autômato para por
indefinição.
Exemplo:
q0 q4q3
0 0
0,1 0,1
q1
q2
1
1
0,1
• q0 tem duas transições com zero.
• q0 tem duas transições com um.
• q1 não tem transição com zero.
• q3 não tem transição com um.
Exemplo:
q0 q4q3
0 0
0,1 0,1
q1
q2
1
1
0,1
• K =
• Σ =
• s =
• F =
• ∆
{q0, q1, q2, q3, q4}
{0, 1}
q0
{q2, q4}
Exemplo: ∆ dada pela tabela:
 0 1
q0
q1
{q0,q3} {q0,q1}
q2
q2
q3
q4
q2q2
q4
q4 q4


M é um Autômato Finito Não Determinístico,
pois:
• (q0, 0, q0) ∈ ∆ e (q0, 0, q3) ∈ ∆
Observações:
• M aceita 110 pois (q0, 110) ⊦ (q1, 10) ⊦ (q2, 0) ⊦
(q2, λ) e q2 ∈ F.
• M não aceita 010 pois:
(q0, 010) ⊦ (q0, 10) ⊦ (q1, 0) ⊦ Para
(q0, 010) ⊦ (q3, 10) ⊦ Para
• M aceita 110 pois:
1
q0 q1 q2
1
q2
0
q2

 Estado
Final
Como se chegou a um estado final {q2} por pelo menos um
caminho, então a palavra 110 é aceita (reconhecida) pelo AFND.
q0
1 1
q0
1
 Não é 
Estado Final
0
Para
0
q1
q0
0
q3

q3
q0

 Não é 
Estado Final
• M não aceita 010 pois:
q0 q0
0
q3
0
Para
1
q1
1
Parou sem
a palavra
toda ser lida
Como não se chegou a nenhum estado final {q2,q4} por
pelo menos um caminho, pois a palavra não foi
totalmente lida, então a palavra 010 não é aceita pelo
AFND.
0
Para
• M aceita 001 pois:
 Estado
Final
Como se chegou a um dos estados finais (q4) por pelo
menos um caminho, então a palavra 001 é aceita
(reconhecida) pelo AFND.
q0 q3
0
q0
0
q4
0 1
Paraq3
0
q0
0
1
q4

q4
1
q1

q1  Não é Estado Final
Exercício: O AFND aceita as cadeias abaixo?
q0 q4q3
0 0
0,1 0,1
q1
q2
1
1
0,1
Utilize a Árvore de Parsing
• 110
• 111
• 010
• 001
• 1000
• 1011
• 0100
• 1101
Sim
Sim
Não
Sim
Sim
Sim
Sim
Sim
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos Finitos Não Determinísticos