Mostrar código-fonte de Autômato finito não determinístico

#REDIRECIONAMENTO [[Máquina_de_estados_finitos_não_determinística]]

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]] <math>L\,\!</math>, é 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 <math>L\,\!</math> 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 <math>\delta</math> definida em <math>Q \times \Sigma \,\!</math>, o seu valor não deve ser um elemento de <math> Q </math> (como acontece com os autômatos determinísticos), mas um subconjunto de <math> Q </math> (incluindo o conjunto vazio). Ou seja, o processamento de <math>\delta(q, a)\,\!</math> leva a um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado <math>q</math> lendo um símbolo de entrada <math>a</math>. 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]] <math>M = (Q, \Sigma, \delta, q_0, F)\,\!</math> onde <math>Q</math> e <math>\Sigma</math> são conjuntos não-vazios, <math>q_0 \in Q</math>, <math> F \subseteq Q </math> e <center><math>\delta:Q \times \Sigma \rightarrow 2^Q</math></center>
<math>Q</math> é o conjunto de estados, <math>\Sigma</math> é o alfabeto, <math>q_0</math> é o estado inicial, <math>F</math> é o conjunto de estados válidos (ou de aceitação) e <math>2^Q</math> 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==

* [http://www.evoluma.com/auger/ Auger] - Software brasileiro com interface gráfica para construção e simulação de autômatos finitos e conversão para outros modelos formais.
* [http://www.simuladordeautomatos.com Simulador de Autômatos] - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
* [http://www.din.uem.br/yandre/sctmf/ SCTMF] - Software para Criação e Teste de Modelos Formais.
* [http://www.jflap.org JFlap] - Software americano para testes com interface gráfica.

==Conceitos relacionados==
* [[Linguagens formais]]
* [[Teoria de autômatos]]
* [[Teoria da computação]]
* [[Teoria dos grafos]]

[[Categoria:Teoria da computação]]