Autômato finito

O autômato finito (em inglês, finite state machine ou finite automaton) é um modelo de computação de um computador primitivo, que se compõe de alguns estados e de algumas transições e que consegue aceitar ou rejeitar uma palavra dada.

Exemplo

De maneira informal, vamos descrever o autômato finito por meio de um diagrama de estados:

O autômato é formado por estados; na figura, são três estados redondos q₀, q₁ e q₂. Entre esses estados há transições, que são aquelas setas. No autômato deve haver ainda um estado inicial, que é o estado q₀. O estado inicial costuma ser representado com uma seta que chega a ele sem partir de nenhum estado. Além disso, no autômato normalmente existe um estado final, que representamos com uma linha dupla; na figura, é o estado q₂.

Um autômato assim construído aceita certas palavras. Damos ao autômato algumas palavras, e ele tenta aceitá-las. Se aceitar, o autômato responde SIM; se não aceitar, responde NÃO. O nosso autômato tenta aceitar palavras compostas das letras “a, b, c”, então podemos tentar fazê-lo aceitar a palavra “abbc”.

Começamos no estado inicial q₀, e na entrada está a palavra “abbc”. Daí em diante vamos seguir as setas.

Percorremos a palavra da maneira usual, da esquerda para a direita, ou seja, o primeiro símbolo que tomamos é o “a”. A seta para a entrada “a” vai para o estado q₁, então passamos para lá e retiramos o símbolo “a” da palavra. Na entrada fica a palavra “bbc”:

A seta para a entrada “b” volta para o nó q₁. De novo retiramos a primeira letra, e na entrada fica a palavra “bc”. Mais uma vez permanecemos no estado q₁. Por fim, na entrada temos a palavra “c”. Do estado q₁, a seta para a entrada “c” nos manda para o estado q₂.

Já esgotamos todas as letras da palavra de entrada e estamos no estado q₂, que é um estado final. Esse autômato finito aceita, portanto, a palavra “abbc”.

Se no fim não estivéssemos em um estado final, o autômato não aceitaria a palavra. Da mesma forma, o autômato não aceitaria a palavra se em algum estado não tivéssemos para onde ir. Por exemplo, para a entrada “ab” chegaríamos ao estado q₁ e pararíamos ali — o autômato não aceita uma palavra assim. Se testássemos a palavra “aabbc”, teríamos azar de novo, porque do estado q₁ não sai seta para a letra “a”.

O autômato finito serve, portanto, para reconhecer um conjunto de palavras. Na prática, poderíamos usar um autômato, por exemplo, para descobrir se a palavra de entrada dada é um e-mail válido.

Definição de autômato finito

Precisamos formalizar a ideia intuitiva anterior do que é um autômato finito, para podermos trabalhar melhor com autômatos daqui para a frente.

Dizemos que um autômato finito (determinístico) é uma quíntupla ⟨Q, Σ, δ, q₀, F⟩, em que

• Q é um conjunto finito de estados,
• Σ (sigma maiúsculo) é o alfabeto (um conjunto finito de símbolos/letras),
• δ: Q × Σ ⟶ Q é a função de transição,
• q₀ ∈ Q é o estado inicial,
• F ⊆ Q é o conjunto dos estados finais (de aceitação).

Voltando ao autômato anterior,

podemos dizer que no conjunto de estados Q há três estados, Q = {q₀, q₁, q₂}. O alfabeto Σ contém as letras com que podemos formar as palavras que o autômato depois vai aceitar ou rejeitar. Aqui, provavelmente será o alfabeto Σ= {a, b, c}, mas pode ser também qualquer superconjunto dele. O estado inicial q₀ é o estado q₀; quanto a isso, nada muda. O conjunto dos estados finais tem, nesse autômato, apenas um estado, F = {q₂}.

Por função de transição entendemos, então, aquelas três setas com letras. Se a notação δ: Q × Σ ⟶ Q confunde você, ela apenas significa que δ é uma função que recebe dois parâmetros: um estado de Q e uma letra de Σ. Ao ser chamada, a função devolve um novo estado. A nossa função de transição poderia ser definida por uma tabela assim:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Se chamarmos δ(q₁, c), aplicamos a terceira linha e a função responde com o estado q₂ — exatamente como o diagrama. Se estamos no estado q₁ e na entrada está a letra “c”, chegamos ao estado q₂. Antes de definirmos formalmente o que significa um autômato aceitar uma palavra, vamos usar a compreensão intuitiva desse conceito e ver alguns outros exemplos.

Outros exemplos

1. Construa um autômato que trabalhe sobre o alfabeto binário, isto é, Σ= {0, 1}, e aceite apenas as palavras que terminam em um. Por exemplo, ele aceita as palavras 1, 01, 000001, 0101011.

   

   O nosso autômato tem dois estados — o inicial q₀ e o final q₁. Sempre que temos na entrada o algarismo 1, passamos para o estado final q₁ e permanecemos nele. Por outro lado, se na entrada está o algarismo 0, passamos para o estado não final q₀ e também permanecemos nele.

2. Construa um autômato sobre o alfabeto binário que aceite apenas as palavras cuja letra inicial seja diferente da letra final.

   

   Logo no primeiro passo, o autômato se divide em dois “subautômatos”. Se a palavra começa com zero, o autômato entra na parte da esquerda e já fica lá; se começa com um, vai para a parte da direita. Depois é o de sempre: se estamos na parte da esquerda e na entrada aparece 1, passamos para o estado final e ficamos nele. Se na entrada aparece 0, passamos para o estado q₁, que não é final.

   Ao contrário dos autômatos anteriores, este autômato tem vários estados finais, isto é, F = {q₃, q₄}.

3. Construa um autômato sobre o alfabeto binário que aceite apenas as palavras que não contenham dois zeros seguidos.

   

   Esse autômato é interessante por duas razões: a primeira é que ele aceita a palavra vazia. Podemos tentar dar a palavra vazia ao autômato, e ele a aceita se o estado inicial for ao mesmo tempo um estado final, o que acontece neste autômato. Como a palavra vazia é uma palavra que não contém dois zeros seguidos, isso está correto. A outra curiosidade é que este autômato tem todos os estados finais. O único caso em que o autômato não aceitaria uma palavra é quando de um estado não saísse nenhuma transição. Isso acontece no estado q₁, que não tem transição para 0, porque aí a palavra conteria dois zeros seguidos.

4. Construa um autômato sobre o alfabeto {-,+,.,0,1,…,9} que aceite apenas as palavras que representam um número. Isso quer dizer ou um número inteiro, como 2, 548, 98263, ou um número decimal, como 5584.48, 3.14 (aqui o separador decimal é o ponto, como nas linguagens de programação), e ambos também na versão para número negativo, com o sinal de menos: -2, -548, -3.14, e também com o sinal de mais escrito explicitamente, isto é, +2, +548, +3.14. Ao mesmo tempo, devemos ser capazes de escrever o número 0.123 apenas como .123 (sem o zero no começo), inclusive com os dois sinais. Vamos introduzir uma notação auxiliar: em vez de escrever dez transições para os dez algarismos, usaremos o símbolo N.

   

5. Construa um autômato sobre o alfabeto binário que aceite apenas as palavras da forma 0ⁿ1ⁿ, o que significa que as palavras têm no início certa quantidade de zeros e em seguida a mesma quantidade de uns. Exemplos dessas palavras são 0011, 00001111, 01.

   Não é possível montar um autômato assim, porque não conseguimos “memorizar” em lugar nenhum a quantidade de zeros. Teríamos de criar vários “subautômatos”, como no segundo exemplo, só que esses “subautômatos” teriam de ser infinitos, um para cada valor de n.

Formalização da computação do autômato

Já definimos formalmente o próprio autômato finito. Agora ainda precisamos definir o que esse autômato de fato faz, isto é, definimos a computação do autômato.

Configuração do autômato: dizemos que um par ⟨q, w⟩ ∈ Q × Σ^∗ é uma configuração do autômato, em que q é o estado atual em que o autômato se encontra e w é a parte ainda não lida da palavra. Σ^∗ representa o fecho do alfabeto Σ, o conjunto de todas as palavras que se podem formar com as letras do alfabeto Σ. Faz parte do fecho também a palavra vazia, que representamos por ε.

Se temos o autômato ⟨Q, Σ, δ, q₀, F⟩ e tentamos aceitar a palavra w, então o autômato se encontra na configuração inicial ⟨q₀, w⟩. Se voltarmos ao autômato

e quisermos aceitar a palavra w = abbc, a configuração inicial será ⟨q₀, abbc⟩.

Definimos o passo de computação como uma relação ↦ entre os conjuntos (Q × Σ^∗) × (Q × Σ^∗), isto é, entre configurações do autômato. Seja w = w₀w₁… w_n a parte ainda não lida da palavra w. Então dizemos que os pares ⟨q₁, w₀w₁… w_n⟩ e ⟨q₂, w₁… w_n⟩ estão na relação ↦, o que escrevemos como

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

se, e somente se, δ(q₁, w₀) = q₂. Voltando ao nosso exemplo, a configuração inicial é ⟨q₀, abbc⟩. Pelo diagrama vemos que, para a entrada “a”, podemos avançar para o estado q₁. Podemos então escrever

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

porque vale δ(q₀, a) = q₁. Com isso fizemos um passo de computação — olhamos para qual estado deveríamos ir com a entrada dada (= a primeira letra da parte ainda não lida da palavra), passamos para lá e removemos a primeira letra da parte não lida da palavra. Assim obtivemos uma nova configuração.

O fecho reflexivo e transitivo da relação passo de computação se representa por ↦ ^∗. Se escrevermos K₁ ↦ ^∗ K₂, em que K₁, K₂ são configurações do autômato, isso significa que, da configuração K₁, por meio de vários passos de computação, conseguimos chegar à configuração K₂, ou seja, existe uma sequência finita de configurações tal que:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Por exemplo, no nosso autômato vale ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, porque, quando fazemos dois passos de computação, sobra a palavra “bc” e permanecemos no estado q₁. Ou seja, existe esta sequência de configurações:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

O autômato aceita a palavra w se, e somente se, existe q_f ∈ F tal que $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Isso significa que o autômato aceita a palavra w se, e somente se, existe uma sequência de passos de computação tal que, no fim dessa sequência, tenhamos lido a palavra inteira e estejamos em um estado final do autômato. O fato de termos lido a palavra inteira é expresso pela presença, na configuração, da palavra ε no lugar da palavra, que é a palavra vazia. O nosso autômato aceita a palavra abbc, porque existe esta sequência de configurações:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

e o estado q₂ é um estado final, q₂ ∈ F.

A linguagem aceita por um autômato é o conjunto de todas as palavras que o autômato aceita. A linguagem do autômato A será representada por L(A). Vale, então, que L(A) ⊆ Σ^∗ e

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ aceita a palavra }w\}$$

Uma linguagem regular é uma linguagem que é aceita por algum autômato finito.

Dois autômatos finitos são equivalentes se aceitam a mesma linguagem. Ou seja, os autômatos A₁ e A₂ são equivalentes se vale L(A₁) = L(A₂).

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools