Autômato finito não determinístico

Embora na prática seja inviável a implementação de autômatos finitos não determinísticos (AFND), esses possuem algumas vantagens sobre os autômatos puramente determinísticos, sobretudo quanto à facilidade de representação em diagramas (ver grafo). Na tentativa de obtenção de um autômato finito para reconhecer certa linguagem regular ${\displaystyle L\,\!}$, é mais natural, em muitos casos, pensar-se primeiramente em representações não determinísticas. Assim, dado que um AFND é uma generalização de um autômato finito determinístico (AFD), é sempre possível encontrar um AFD equivalente que reconheça ${\displaystyle L\,\!}$ a partir de um dado AFND (possivelmente através de um algoritmo de construção de subconjuntos), o que torna a implementação viável.

Descrição básica

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. Portanto, para uma função de transição ${\displaystyle \delta }$ definida em ${\displaystyle Q\times \Sigma \,\!}$, o seu valor não deve ser um elemento de ${\displaystyle Q}$ (como acontece com os autômatos determinísticos), mas um subconjunto de ${\displaystyle Q}$ (incluindo o conjunto vazio). Ou seja, o processamento de ${\displaystyle \delta (q,a)\,\!}$ leva a um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado ${\displaystyle q}$ lendo um símbolo de entrada ${\displaystyle a}$. Assim, podemos definir um autômato finito não determinístico matematicamente como se segue.

Definição formal

Um autômato finito não determinístico é uma quíntupla ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)\,\!}$ onde ${\displaystyle Q}$ e ${\displaystyle \Sigma }$ são conjuntos não-vazios, ${\displaystyle q_{0}\in Q}$, ${\displaystyle F\subseteq Q}$ e

${\displaystyle \delta :Q\times \Sigma \rightarrow 2^{Q}}$

${\displaystyle Q}$ é o conjunto de estados, ${\displaystyle \Sigma }$ é o alfabeto, ${\displaystyle q_{0}}$ é o estado inicial, ${\displaystyle F}$ é o conjunto de estados válidos (ou de aceitação) e ${\displaystyle 2^{Q}}$ significa o conjunto das partes de Q.

Referências

Martin, John C. - Introduction to languages and the theory of computation (2ª Edição)

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman – Introdução à Teoria de Autômatos, Linguagens e Computação (2ª Edição).

Softwares

• Auger - Software brasileiro com interface gráfica para construção e simulação de autômatos finitos e conversão para outros modelos formais.
• 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.

Conceitos relacionados

• Linguagens formais
• Teoria de autômatos
• Teoria da computação
• Teoria dos grafos