AFD e AFND

Um autômato finito determinístico (AFD) é a quíntupla (Q, Σ, δ, q₀, F): estados finitos, alfabeto, transição total δ: Q×Σ → Q com um sucessor por par, inicial e finais. Aceita a cadeia se o único percurso termina em F.

AFND, expressões e fechamento deste tópico — e gramáticas livres de contexto e autômatos com pilha nos seguintes — partem dessa máquina de memória finita e de L(A).

As páginas se agrupam em cinco blocos. O primeiro define o reconhecedor: um sucessor no AFD; conjunto de destinos e ε-transição no AFND.

O segundo converte entre formalismos da mesma classe: construção por subconjuntos, ida e volta com expressão regular, cabeça L/R.

O terceiro produz saída: Moore no estado, Mealy na transição.

O quarto fecha a classe: opera as máquinas ou só enuncia o que permanece regular.

O quinto testa regularidade e compara duas máquinas: bombeamento, índice de Myhill–Nerode, minimizar ou vacuidade da diferença simétrica.

Autômatos Finitos Determinísticos (AFD) segue o único sucessor e aceita em F. Autômatos Finitos Não Determinísticos (AFND) admite conjunto de destinos e ε; aceita se algum caminho chega a F.

Converter o AFND no AFD equivalente, com fecho-ε, está em Equivalência entre AFND e AFD. A tabela de pares distinguíveis, ou um par final alcançável no produto, está em Algoritmos de Decisão Regulares.

Produto (q₁, q₂) e inverter F estão em Propriedades de Fechamento de Linguagens Regulares. Enunciar união, concatenação, estrela, ∩ e reverso, sem redesenhar, está em Propriedades de Conjuntos Regulares.

Exibir s = xyz que sai de L ao repetir ou apagar y está em Lema do Bombeamento. Contar as classes de prefixos distinguíveis por sufixo, ou concluir índice infinito, está em Teorema de Myhill-Nerode.