Máquina de estados finitos determinística

Na teoria dos autômatos, uma máquina de estados finita determinística ou autômato finito determinístico (AFD) é uma máquina de estados finitos onde, dado uma configuração e um símbolo da cadeia de entrada existe somente um estado para o qual a máquina pode transitar. Em outras palavras, em um AFD, o estado sucessor é definido unicamente pelo seu estado atual e pela condição de transição.

Definição formal

Um autômato finito determinístico é formalmente definido por uma quintúpla:

$M=(Q,\ \Sigma,\ \delta,\ q_{0},\ F)$

Onde:

• $\, Q$ é um conjunto finito de estados.
• $\,\Sigma$ é um conjunto finito de símbolos, denominado alfabeto de entrada.
• $\,\delta:Q \times \Sigma \to Q$ é a função de transição.
• $\,q_{0}\in\, Q$ é o estado inicial.
• $F\subseteq Q$ é o conjunto de estados finais (ou de aceitação).

Nesta formulação do AFD, a condição de que as todos os estados tenham apenas uma transição para cada símbolo do alfabeto é garantida pela relação de transição que está definida como uma função de $Q$ e $\Sigma$. Como uma função mapeia, para cada elemento do domínio, apenas um elemento do contra-domínio, a função $\delta$ mapeia, para cada par estado-símbolo, apenas um estado destino.

A princípio, a função $\delta$ é injetora, no entanto, em algumas definições é possível observar que transições indesejadas são removidas a fim de tornar a descrição do AFD mais simples. Neste caso, caso não haja uma transição definida para um determinado símbolo do alfabeto, fica subentendido que o autômato termina sua execução, rejeitando a cadeia de entrada.

Esta generalização da definição não modifica o funcionamento base do autômato nem sua característica determinística, uma vez que é possível tornar a função injetora incluindo um estado adicional $q_{erro}$ e substituir a função $\delta_{ant}$ pela função $\delta_{novo}$, respeitando as especificações abaixo:

$q_{erro} \in Q$

$q_{erro} \notin F$

$\mbox{se } (q_i,\sigma,q_j) \notin \delta_{ant} \Rightarrow (q_i,\sigma,q_{erro}) \in \delta_{novo} \qquad \forall q_i, q_j \in Q-\left\{q_{erro} \right\} \mbox{ e } \forall \sigma \in \Sigma$

$(q_{erro},\sigma,q_{erro}) \in \delta_{novo} \qquad \forall \sigma \in \Sigma$

Com isso, todas transições não existentes são incluídas, fazendo com que o autômato transite para um estado não terminal que "aprisiona" o mesmo até que a cadeia seja completamente consumida.

Softwares

• Simulador de Autômatos - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
• SCTMF - Software para Criação e Teste de Modelos Formais.
• JFlap - Software americano para testes com interface gráfica.

Ver também

• Máquina de estados finitos não determinística