Autômatos

Autômatos Finitos

Autômato finito é um modelo matemático usado para representar programas de computador ou circuitos lógicos. O conceito é concebido como uma máquina abstrata que deve estar em um de seus finitos estados. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.
São procedimentos aceitadores, ou reconhecedores, pode conter uma quantidade finita e limitada de informação. Essa informação é representada por um estado da máquina, e só existe um número finito de estados. Essa restrição faz com que o autômato finito seja severamente limitado na classe de linguagens que são reconhecidas.

Máquinas de estado finito podem modelar um grande número de problemas, entre os quais a automação de design eletrônico, projeto de protocolo de comunicação, análise e outras aplicações de engenharia. Na biologia e na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, utilizadas para descrever sistemas neurológicos e em lingüístico para descrever as gramáticas das linguagens naturais.

Não determinístico
A função de transição de um autômato finito não determinístico não precisa determinar exatamente qual deve ser o próximo estado. Em vez disso, a função de transição fornece uma lista (um conjunto) de estados para os quais a transição poderia ser feita. Essa lista pode ser vazia, ou ter um número qualquer positivo de elementos. Essa possibilidade de escolha entre vários caminhos a serem seguidos nos leva a modificar a definição de aceitação. Um afd aceita se "o último estado atingido é final";
Mas um afnd aceita uma