Autômatos finitos

Os símbolos que deverão ser reconhecidos na análise léxica são representáveis por expressões regulares (Seção 3.1.4) ou equivalentemente por gramáticas regulares (tipo 3). Existe também uma correspondência unívoca entre expressões (ou gramáticas) regulares e autômatos finitos, máquinas que podem ser utilizadas para reconhecer strings de uma dada linguagem.

Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. À medida que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro, segundo um conjunto de regras de transição especificadas para o autômato. Se após o último carácter o autômato encontra-se em um dos estados finais, a string foi reconhecida (ou seja, pertence à linguagem). Caso contrário, a string não pertence à linguagem aceita pelo autômato.

Formalmente, um autômato é descrito por cinco características,

1. um conjunto finito de estados, $K$,
2. um alfabeto de entrada finito, $\Sigma$,
3. um conjunto de transições, $\delta$,
4. um estado inicial, $S$, onde $S \in K$,
5. um conjunto de estados finais, $F$, onde $F \subseteq K$

sendo portanto representável por uma quíntupla $M = (K,\Sigma,\delta,S,F)$.

As transições são representadas por triplas $(s_i, \Sigma_T, s_f)$, onde $s_i$ é um estado inicial da transição, $\Sigma_T$ é o conjunto de símbolos do alfabeto (caracteres) que disparam esta transição quando o estado corrente é $s_i$ e $s_f$ será o novo estado corrente do autômato após a transição.

Autômatos são usualmente representados na forma de um grafo dirigido, onde estados são representados por círculos, sendo que estados finais são representados por círculos duplos, e as transições por arestas rotuladas com os símbolos que disparam a transição entre os dois estados conectados (Figura 3.2).

Figura: Representação gráfica de $(s_i, \{a\}, s_f)$, denotando a transição de $s_i$ (estado não final) para $s_f$ (um estado final) disparada pelo símbolo $a$.

Uma outra forma de representar um autômato, mais apropriada para fins de processamento automático, é através de tabelas de transição. Uma tabela de transição é uma matriz na qual as colunas representam os estados do autômato e as linhas os símbolos do alfabeto. Cada entrada na matriz indica qual o estado final de uma transição a partir do estado indicado na coluna através do símbolo indicado na linha. Assim, a transição expressa na Figura 3.2 poderia ser equivalentemente representada por

	...	$s_i$	...
$a$	...	$s_f$	...
...	...	...	...

Assim, colunas da tabela de transição representam o estado corrente e as linhas, o símbolo corrente. Uma entrada na tabela (cruzamento entre linha e coluna) pode ser vazia, indicando que não há transição possível, ou ter o próximo estado que é atingido pela transição corrente.

Autômatos finitos podem ser determinísticos, quando para cada combinação de estado e entrada existe uma única transição aplicável, ou não-determinísticos em caso contrário. É possível mostrar que a cada autômato finito não-determinístico corresponde um autômato finito determinístico que aceita a mesma linguagem.