Autômato finito

Linguagens Formais
Capítulo 4: Autômatos finitos e expressões regulares
– com Luiz Carlos Castro Guedes
4.1 - Introdução
Neste capítulo estudaremos uma máquina (um procedimento aceitador, ou reconhecedor), chamada autômato finito (af). A palavra finito é incluída no nome para ressaltar que um af só pode conter uma quantidade finita e limitada de informação, a qualquer momento. 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 af seja severamente limitado na classe de linguagens que pode reconhecer, composta apenas pelas linguagens regulares, como mostraremos neste capítulo.
Duas versões do af são estudadas aqui: o af determinístico (afd) e o af não determinístico (afnd). Este capítulo mostra que uma linguagem regular pode ser definida de quatro formas:
•
•
•
•

através de uma gramática regular (definição); através de um afd que reconhece a linguagem; idem, através de um afnd; através de uma expressão regular, um mecanismo a ser introduzido com essa expressa finalidade.

4.2 - Autômato finito determinístico
Como observado acima, a informação que um af guarda sobre a entrada (mais precisamente sobre a parte da entrada já lida) é representada por um estado, escolhido em um conjunto finito de estados. A definição formal de automato finito, na sua versão determinística é dada a seguir.
Definição. Um Autômato Finito Determinístico (afd) M, sobre um alfabeto Σ é um sistema (K, Σ, δ, i, F), onde
K é um conjunto de estados finito, não vazio;
Σ é um alfabeto de entrada (finito) δ: K×Σ → K é a função de transição i∈K é o estado inicial
F⊆K é o conjunto de estados finais.
O nome determinístico faz referência ao fato de que δ é uma função (também chamada função próximo-estado), que determina precisamente o próximo estado a ser assumido quando a máquina M se encontra no estado q e lê da entrada o símbolo a: o estado δ(q, a).

J. L. Rangel, L. C. Guedes - Ling.