Autómatos

Para além das gramáticas regulares e expressões regulares, a sintaxe de uma linguagem regular, pode ser caracterizada por autómatos finitos.

Os autómatos finitos podem ser entendidos como a idealização de um computador que tem acesso apenas a uma quantidade limitada de memória. Computadores deste tipo podem ser utilizados para controlar um elevador, as portas automáticas de um banco, o dispositivo de injecção de um motor de combustão interna, etc.

Nesta secção, damos preferência a representações gráficas de autómatos finitos, por meio de diagramas. Limitamos no entanto a exposição a autómatos finitos deterministas. Abaixo apresentamos o exemplo dum diagrama que representa um autómato deste tipo. Estas representações gráficas são usualmente designadas de diagramas de estados.

Um autómato é definido por vários estados, representado por círculos, no exemplo os estados são $q_1,q_2,q_3,q_4$. Um dos estados é identificado como estado inicial, no exemplo $q_1$. Associado a um autómato está sempre um alfabeto $\Sigma$, no exemplo $\Sigma=\{0,1\}$. Os símbolos do alfabeto são usados para rotular os arcos (setas) do autómato. Dado um estado tem de haver sempre uma transição para outro estado (possivelmente ele próprio) associada a cada elemento um dos símbolos em $\Sigma$. No nosso exemplo, para cada estado, existe sempre duas transições, uma associada ao símbolo 0 e a outra ao símbolo 1. Todas as possíveis transições devem estar definidas, podendo um arco ter associado mais do que um símbolo.

O input para um autómato de alfabeto $\Sigma$ é uma palavra em $\Sigma^\ast$, que é aceite ou rejeitada pelo autómato. Supondo que o input, no exemplo é, $w=0110$. Inicialmente a computação tem início no estado $q_1$. O autómato lê o primeiro símbolo, que é 0. A regra de transição determina que, caso esteja em $q_1$ e se esteja a ler um 0, o estado do autómato deve continuar a ser $q_1$. Lendo depois o próximo símbolo da palavra, que é um 1. A regra de transição determina que, caso esteja em $q_1$ e se esteja a ler um 1, o estado do autómato deve passar a ser $q_2$. Lendo depois o próximo símbolo da palavra, que é outro 1. A regra de transição determina que, caso esteja em $q_2$ e se esteja a ler um 1, o estado do autómato passa a ser $q_3$. O próximo símbolo é um 0, a regra de transição determina que, o estado do autómato deve continuar a ser $q_3$. Como não existem mais símbolos na palavra para serem lidos a computação termina, no estado $q_3$.

Uma palavra é aceite pelo autómato caso a computação termine num estado terminal. No diagrama de estado identificamos estados terminais por um duplo ciclo. No exemplo, o autómato só tem um estado terminal $q_4$, como a computação da palavra $w=0110$ não termina num estado terminal, diz-se que $w$ não é aceite ou reconhecida pelo autómato.

Descrevemos abaixo a computação, agora da palavra $w=011011$, através duma tabela. A primeira coluna representa o estado do autómato, num dado momento, e o símbolo da coluna da direita é o símbolo que está a ser lido:

A computação tem assim início no estado $q_1$, a leitura progressiva de símbolos $0,1,1,0,1$ e $1$, faz com que o autómato assuma progressivamente os estados $q_1,q_2,q_3,q_3,q_4,$ e $q_5$, terminando a computação no estado $q_5$, por falta de mais símbolos para ler. Como $q_5$ é estado terminal a palavra $011011$ diz-se reconhecida pelo autómato.

Podemos assim diz-se que, as palavras reconhecidas por um autómato definem caminhos no diagrama de estados, que partindo do estado inicial, permitem chegar a um dos estados terminais.

Devemos notar ainda que a relação de transição num autómato finito pode ser sempre descrita por uma aplicação $t$. Identificando por $E$ o conjunto de estados e por $\Sigma$ o alfabeto, a relação de transição é uma aplicação: $$ t:E\times \Sigma\rightarrow E. $$ No exemplo apresentado acima, esta aplicação pode ser descrita pela tabela abaixo:

Que indica que, quando no estado $q_2$, por exemplo, caso esteja a ler um 0 passa para o estado $q_2$, caso esteja a ler um 1 passa para o estado $q_3$.