Tema 02

Prévia do material em texto

Linguagens Formais
Tema 2 – Autômato Finito 
Não-Determinístico
Professor Sérgio Assunção Monteiro, DSc
REFORÇANDO A 
APRENDIZAGEM
PONTOS PRINCIPAIS
Autômato Finito Não-Determinístico
Fundamentos
Um Autômato Finito Não-Determinístico M é uma 5-
tupla dada por: 
M = (Q, Σ, ρ, q0, F) consistindo de:
• Σ : conjunto finito de símbolos de entrada chamado 
Alfabeto;
• Q : conjunto finito de estados;
• ρ : função de transição de estados (ρ: Q × Σ → 2Q);
• q0 : estado inicial (q0 ∈ Q) e
• F : conjunto de estados de finais ou estados de 
aceitação (F⊆ Q).
https://pt.wikipedia.org/wiki/Enupla
Autômato Finito Não-Determinístico
Exemplo
Seja M = (S, Σ, ρ, q0, F), onde 
Q = {q0, q1, q2 }, Σ ={a, b}, F = {q2}
Estado (Q) ρ
Entrada ( Σ )
a b
q0 {q0, q1} {}
q1 {q1, q2} {q1}
q2 {} {}
Autômato Finito Não-Determinístico
Representação Gráfica
Autômato Finito Não-Determinístico
Processamento de Palavras
Processar a palavra: aaa
Ciclo t0 t1 t2 t3
Entrada a a a -
Proc1 Estado q0 q0 q0 q0
Proc2 Estado q0 q0 q0 q1
Proc3 Estado q0 q0 q1 q1
... ... ... ... ... ...
Autômato Finito Não-Determinístico
Converter AFN para AFD
Obter o AFD do AFN dado por M = (Q, Σ, ρ, q0, F), onde
Q = {q0, q1, q2 }, Σ ={a, b}, F = { q2 } e δ é dado pela tabela 
abaixo: 
Estado (Q) ρ
a b
q0 {q1, q2} {}
q1 {q2} {q0, q2}
q2 {q2} {q0}
Autômato Finito Não-Determinístico
Solução: 1. Obter novos estados
δ a b
s0 = {q0} ? ?
s1 = {q1} ? ?
s2 = {q2} ? ?
s3 = {q0, q1} ? ?
s4 = {q0, q2} ? ?
s5 = {q1, q2} ? ?
s6 = {q0, q1, q2} ? ?
s7 = {} ? ?
Autômato Finito Não-Determinístico
Solução: 2. Localizar os estados finais
δ a b
s0 = {q0} ? ?
s1 = {q1} ? ?
s2 = {q2} ? ?
s3 = {q0, q1} ? ?
s4 = {q0, q2} ? ?
s5 = {q1, q2} ? ?
s6 = {q0, q1, q2} ? ?
s7 = {} ? ?
Autômato Finito Não-Determinístico
Solução: 3. Obter transições
δ a b
s0 = {q0} s5 s7
s1 = {q1} s2 s4
s2 = {q2} s2 s0
s3 = {q0, q1} s5 s4
s4 = {q0, q2} s5 s0
s5 = {q1, q2} s2 s4
s6 = {q0, q1, q2} s5 s4
s7 = {} s7 s7
Autômato Finito Não-Determinístico
Detalhando o passo 3
• δ(s0, a) = ρ(q0, a) = {q1, q2} = s5
• δ(s0, b) = ρ(q0, b) = {} = s7
• δ(s3, a) = ρ(q0, a) U ρ(q1, a) = {q1, q2} U { q2} = {q1, q2} = s5
• δ(s3, b) = ρ(q0, b) U ρ(q1, b) = {} U {q0, q2} = {q0, q2} = s4
Autômato Finito Não-Determinístico
Solução: 4. Eliminar estados inalcançáveis
δ a b
s0 = {q0} s5 s7
s2 = {q2} s2 s0
s4 = {q0, q2} s5 s0
s5 = {q1, q2} s2 s4
s7 = {} s7 s7
Ninguém chega a s1 , s3 e s6
Autômato Finito Não-Determinístico
Solução: 5. Desenhar o diagrama do AFD
Devemos eliminar s7
Autômato Finito Não-Determinístico
Solução: 6. Versão final do AFD
Autômato Finito Não-Determinístico
Exercícios
Seja M = (S, Σ, ρ, q0, F), onde Q = {q0, q1, q2 }, Σ ={a, b}, 
F = {q2} e ρ é dado pela tabela abaixo.
Obtenha o AFD equivalente.
Estado (Q) ρ
Entrada ( Σ )
a b
q0 {q0} {q0, q1}
q1 {} {q2}
q2 {} {}
Autômato Finito Não-Determinístico
Prática: exemplo no colab
biblioteca: automata
url: https://github.com/caleb531/automata
https://github.com/caleb531/automata