Conceitos
Autômatos Finitos Determinísticos
Como definição de Autômato Finito Determinístico (AFD) podemos dizer que é uma quíntupla ordenada A = (Q, Ʃ, δ, qo, F)
Onde:
Q é um conjunto finito, não vazio, de estados;
Ʃ é um conjunto finito (alfabeto) de símbolos de entrada;
δ: Q X Ʃ -> Q é a função (parcial) de transição ou de mudança de estado;
qo Є Q é o estado inicial;
F ⊆ Q é o conjunto dos estados finais de aceitação.
Como exemplo citaremos o autômato finito A = ({q0, q1, q2, qf}, {a, b} d1, q0, {qf}) , onde d1 é representada pela tabela abaixo, reconhece a linguagem
L = {w | w possui aa ou bb como subpalavra}
|
d1 |
a |
b |
|
q0 q1 q2 qf |
q1 qf q1 qf |
q2 q2 qf qf |
Autômatos Finitos Não Determinísticos
Autômatos finitos não determinísticos diferem dos Autômatos finitos determinísticos quanto à regra de transição entre estados. Dada uma combinação de um estado atual e um símbolo de entrada, pode não haver estados especificados para os quais o estado atual deve conduzir o processamento, bem como pode haver vários estados resultantes da leitura do símbolo.
O conceito de não-determinismo de um autômato significa que:
• a função de transição pode conduzir a múltiplos estados, ou mesmo a nenhum estado;
• podem ocorrer transições por ε.
Casos de não-determinismo:
Um Autômato Finito Não - Determinístico (AFN) é uma quíntupla ordenada, A = (Q, Σ, δ, q0, F)
onde:
• Q é um conjunto finito, não vazio, de estados ,
• Σ é um conjunto finito (alfabeto) de símbolos de entrada,
• δ: Q X ( Σ ∪ {ε} ) → 2Q é a função de transição ou de mudança de estado,
• q0 ∈ Q é o estado inicial,
• F ⊆ Q é o conjunto dos estados finais ou de aceitação.
Exemplo 1: um AFN reconhecedor das cadeias binárias terminadas em 01.
Diagrama de transições:
