Autómatos finitos

Um autómato é uma “máquina” que executa sobre uma determinada sequência de entradas passo a passo (de forma discreta no tempo).

Internamente, o autómato contém uma máquina de estados, que vai evoluindo até uma de duas possibilidades: aceitar ou rejeitar a entrada.

A palavra de entrada será reconhecida se o estado final for de aceitação.

Um autómato finito é caracterizado por definir uma máquina de estados finita, em que as transições de estados apenas têm em conta o estado actual e a entrada.

Graficamente, associam-se círculos aos estados e anota-se as transições entre estados com as entradas correspondentes (estados de aceitação terão um círculo duplo).

Os autómatos finitos são classificados em dois tipos:

• Autómato finito não determinista (AFND): não existem restrições às condições colocadas nas transições. O mesmo símbolo (entrada) pode anotar várias transições a partir do mesmo estado, sendo também permitidas transições com a palavra vazia (ε).

• Autómato finito determinista (AFD): cada estado indica no máximo uma transição com cada símbolo do alfabeto.

Qualquer um destes tipos de autómatos reconhece as mesmas linguagens, e demonstra-se que essas linguagens correspondem às linguagens regulares.

Note que um AFD é um caso particular de um AFND.

Os autómatos finitos podem ser completos ou incompletos.

Será incompleto caso não existam transições para todos os símbolos do alfabeto, e completo no caso contrário.

Neste caso, o aparecimento desse símbolo com o autómato nesse estado, leva imediatamente à rejeição da palavra.

Podemos sempre converter um autómato incompleto num completo destinando todas as transições não expressas para um novo estado que funcione como uma especie de “buraco negro”. Isto é, um estado do qual não se pode sair. Obviamente, esse estado não pode ser de aceitação.