Autômatos finitos não determinísticos
Origem: Wikipédia, a enciclopédia livre.
Embora na prática seja inviável a implementação de autômatos finitos não determinísticos (AFN), 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 
, é mais natural, em muitos casos, pensar-se primeiramente em representações não determinísticas. Assim, dado que um AFN é uma generalização de um autômato finito determinístico (AF), é sempre possível encontrar um AF equivalente que reconheça a partir de um dado AFN (possivelmente através de um algorítmo de construção de subconjuntos), o que torna a implementação viável.
Índice |
[editar] 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 δ definida em 
, o seu valor não deve ser um elemento de Q (como acontece com os autômatos determinísticos), mas um subconjunto de Q (incluindo o conjunto vazio). Ou seja, o processamento de 
leva à um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado q lendo um símbolo de entrada a. Assim, podemos definir um autômato finito não determinístico matematicamente como se segue.
[editar] Definição Formal
Um autômato finito não determinístico é uma quíntupla 
onde Q e Σ são conjuntos não-vazios, 
, 
e
Q é o conjunto de estados, Σ é o alfabeto, q0 é o estado inicial, F é o conjunto de estados válidos (ou de aceitação) e 2Q siginifica o conjunto das partes de Q.
[editar] 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).
