Tema 03

Prévia do material em texto

Linguagens Formais
Tema 3 – Autômatos Finitos Não-
Determinísticos com Transições Vazias
Professor Sérgio Assunção Monteiro, DSc
REFORÇANDO A 
APRENDIZAGEM
PONTOS PRINCIPAIS
Autômato Finito Não-Determinístico 
com transições vazias - AFNλ
Fundamentos
Um AFNλ é uma 5-tupla dada por: 
M = (Q, Σ, δ, q0, F)
Onde:
• Σ: alfabeto;
• Q: conjunto finito de estados;
• δ: função programa (δ: Q × (Σ U {λ}) → 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 
com transições vazias - AFNλ
Exemplo
Seja M = (S, Σ, δ, q0, F), onde 
Q = {q0, q1, q2 }, Σ ={a, b}, F = {q0, q2}
Estado (Q) δ
Entrada ( Σ )
0 1 λ
q0 {q0, q1} {} {q2}
q1 {q1} {q1} {q2} 
q2 {q2} {} {}
Autômato Finito Não-Determinístico 
com transições vazias - AFNλ
Representação Gráfica
Autômato Finito Não-Determinístico 
com transições vazias - AFNλ
Conversão de AFNλ para AFN
Nota de aula
Autômato Finito Não-Determinístico 
com transições vazias - AFNλ
Prática: exemplo no colab
biblioteca: automata
url: https://github.com/caleb531/automata
https://github.com/caleb531/automata