Autómatos Finitos Deterministas

Um modelo computacional simples, com memória limitada.

Introdução

Exemplo de um Autómato Finito
O que acontece quando a entrada é $a\AST$?

Para resolver o Problema Principal de ALP é necessário formalizar a noção de “computador/programa”, de forma a representar PL = Super(e).

Os Autómatos Finitos são modelos formais de “computadores/programas” simples de descrever mas capazes de resolver vários problemas teóricos e com algumas aplicações práticas (ver o artigo na wikipedia).

Um autómato tem como entrada uma palavra que é processada símbolo a símbolo até que termina num certo estado. Em certos estados do autómato a palavra, depois de completamente “lida”, é aceite e noutros é rejeitada.

Um autómato pode ser representado por um grafo orientado. Os vértices “são” os estados do autómato e as “arestas” indicam como são “lidos” os símbolos.

Autómato Finito Determinista

Autómato Finito Determinista (AFD). Um Autómato Finito Determinista (AFD) ou Autómato de Estados Finitos (Em inglês: Determinist Finite State Machine (DFSM) ou Determinist Finite State Automaton (DFSA)) é um tuplo $\del{Q, \Sigma, \delta, q_I, F}$ onde:

• Estados de Controlo $Q$ é um conjunto finito.
• Alfabeto de Entrada $\Sigma$ é um alfabeto.
• Transição $\delta: Q \times \Sigma \to Q$ é uma função.
• Estado Inicial $q_I \in Q$.
• Estados Finais ou de Aceitação $F \subseteq Q$.

Intuitivamente, um AFD “anda” de estado em estado, conforme “processa” os símbolos de uma palavra, de acordo com a transição. Esse “passeio” começa no estado inicial e “consome” um símbolo da palavra de cada vez. Quando todos os símbolos estão processados, o AFD fica num certo estado. Se for um dos estados finais a palavra é aceite, caso contrário é rejeitada.

Por exemplo, seja $A = \del{\set{q_0, q_1, q_2, q_3}, \set{0, 1}, \delta, q_0, \set{q_1, q_2}}$ em que a transição $\delta$ é definida pela seguinte tabela: $$ \begin{array}{c|cc} \delta & 0 & 1 \cr \hline q_0 & q_1 & q_2 \cr q_1 & q_2 & q_3 \cr q_2 & q_2 & q_2 \cr q_3 & q_3 & q_3 \end{array} $$

• Os estados de controlo são os elementos de $Q = \set{q_0, q_1, q_2, q_3}$.
• O alfabeto de entrada é $\Sigma = \set{0, 1}$.
• A transição é a função $\delta(q,s) = q’$ em que $q’$ está na linha $q$ e coluna $s$ da tabela acima.
• O estado inicial é $q_I = q_0$.
• Os estados finais são os elementos de $F = \set{q_1, q_2}$.

A função de transição de um AFD é quase sempre representada por uma tabela como no exemplo acima. Mas por vezes é conveniente apresentá-la como um conjunto de triplos: $$\set{\del{i, a, j} \st j = \delta\at{i, a}, i \in Q, a \in \Sigma}.$$

A transição acima como um conjunto de triplos fica: $$\set{\del{q_0, 0, q_1}, \del{q_0, 1, q_2}, \del{q_1, 0, q_2}, \del{q_1, 1, q_3}, \ldots}$$

Configuração, Computação, Aceitação

A computação da palavra $p = 000$ por este autómato é a sequência $$q_0 \trf{0} q_1 \trf{0} q_2 \trf{0} q_2 \in F.$$

A notação $q \trf{a} q’$ indica que o autómato passa do estado $q$ para $q’$ lendo o símbolo $a$. Concatenado todos esses símbolos, da esquerda para a direita, obtém-se a palavra processada, neste caso $p = 000$. Também é indicado que o último estado é final, pelo que a palavra $p$ é aceite pelo autómato $A$.

Configuração. Computação. Palavra Aceite. Seja $A = \del{Q, \Sigma, \delta, q_I, F}$ um AFD.

Uma configuração de $A$ é um par $\del{q, s}\in Q \times \cl{\Sigma}$ onde $q$ é o estado atual e $s$ é o sufixo restante.

A computação da palavra $p = a_1 a_2 \ldots a_n \in \cl{\Sigma}$ pelo AFD $A$ é a sequência de configurações $$\del{q_0, a_1 a_2 \ldots a_n} \vdash_A \del{q_1, a_2 \ldots a_n} \vdash_A \cdots \vdash_A \del{q_n, \nil}$$ em que:

• base (configuração inicial) $q_0 = q_I$.
• passo (processamento do símbolo ativo) $q_i = \delta\del{q_{i-1}, a_i}, i \geq 1$.

Se $q_n\in F$ a palavra $p$ é aceite pelo autómato $A$. Caso contrário, $p$ é rejeitada por $A$.

Por exemplo, aplicando estas definições ao autómato anterior:

1. De acordo com a base, a configuração inicial é $\del{q_0, \underline{0}00}$. O “símbolo ativo” está sublinhado.
2. Aplicando o passo obtém-se a configuração $\del{q_1, \underline{0}0}$ porque $q_1 = \delta\del{q_0, 0}$.
3. O passo é repetidamente aplicado, consumindo o símbolo ativo de cada vez, até que o sufixo restante é $\nil$:
   1. $\del{q_1, \underline{0}0} \vdash \del{q_2, \underline{0}}$.
   2. $\del{q_2, \underline{0}} \vdash \del{q_2, \nil}$.

A computação pode ser visualizada numa tabela, com uma configuração por linha

$$ \begin{array}{c|l} q & s \cr \hline q_0 & 000 \cr q_1 & 00 \cr q_2 & 0 \cr q_2 & \nil \end{array} $$ ou de forma ainda mais compacta: $$ \begin{array}{l} q_0 000 \cr q_1 00 \cr q_2 0 \cr q_2 \nil \end{array} $$ ou ainda $$ q_0 \trf{000} q_1 \trf{00} q_2 \trf{0} q_2 \in F. $$

A computação termina quando não é possível fazer mais transições. Neste exemplo o autómato fica no estado $q_2 \in F$. Portanto $p = 000$ é aceite por $A$.

O que acontece com $p=010$? A computação é a sequência: $$ q_0 \trf{010} q_1 \trf{10} q_3 \trf{0} q_3 \not\in F. $$

Neste caso a computação termina no estado $q_3 \not\in F$. Portanto $010$ é rejeitada por $A$.

Diagramas dos Autómatos Finitos Deterministas

Tal como com as expressões regulares, a visualização gráfica dos autómatos finitos deterministas é uma ferramenta útil.

Diagrama de um AFD. Seja $A = \del{Q, \Sigma, \delta, q_I, F}$ um AFD. O diagrama de $A$ é um grafo orientado em que:

• Os vértices são os estados de controlo $q\in Q$.
• Os arcos são definidos pela transição. Se $q’ = \delta\del{q, a}$ então o diagrama tem o arco
• O (único) vértice com o estado inicial é assinalado por um arco órfã a entrar:
• Os (vários) vértices com estados finais são assinalados por um círculo duplo:

Por exemplo, o AFD usado nos exemplos acima tem o seguinte diagrama:

Diagrama de um AFD

Transição Estendida

A transição de um AFD está definida para cada símbolo do alfabeto de entrada: $\delta: Q \times \Sigma \to Q$. No entanto é mais conveniente estender as transições a palavras: $\hat{\delta}: Q \times \cl{\Sigma} \to Q$.

Transição Estendida. Seja $A=\del{Q, \Sigma, \delta, q_I, F}$ um AFD. A função de transição estendida tem assinatura $\hat{\delta}: Q \times \alert{\cl{\Sigma}} \to Q$ e fica definida pelas seguintes regras recursivas:

• base - palavra vazia $\hat{\delta}\del{q, \nil} = q$.
• base - símbolos Para cada $a \in \Sigma, \hat{\delta}\del{q, a} = \delta\del{q, a}$.
• passo Se $p\in\cl{\Sigma}, a \in\Sigma$ então $\hat{\delta}\del{q, pa} = \delta\del{\hat{\delta}\del{q, p}, a}$.

Intuitivamente, $\hat{\delta}\del{q, p}$ é o estado em que o AFD fica depois de processar a palavra $p$ a partir do estado $q$.

Por exemplo, usando o AFD anterior: $$ \begin{aligned} \hat{\delta}\del{q_0, 000} &= \delta\del{\hat{\delta}\del{q_0, 00}, 0} \cr &= \delta\del{\delta\del{\hat{\delta}\del{q_0, 0}, 0}, 0} \cr &= \delta\del{\delta\del{\delta\del{q_0, 0}, 0}, 0} \cr &= \delta\del{\delta\del{q_1, 0}, 0} \cr &= \delta\del{q_2, 0} \cr &= q_2 \end{aligned} $$ e $$ \begin{aligned} \hat{\delta}\del{q_0, 010} &= \delta\del{\hat{\delta}\del{q_0, 01}, 0} \cr &= \delta\del{\delta\del{\hat{\delta}\del{q_0, 0}, 1}, 0} \cr &= \delta\del{\delta\del{\delta\del{q_0, 0}, 1}, 0} \cr &= \delta\del{\delta\del{q_1, 1}, 0} \cr &= \delta\del{q_3, 0} \cr &= q_3 \end{aligned} $$

Com transições estendidas a escrita de certas definições e condições fica mais compacta e intuitiva:

1. Computação $\hat{\delta}\del{q, p} = q’ \Leftrightarrow \del{q, p} \alert{\vdash_A^{\ast}} \del{q’, \nil}$.
2. Aceitação $p\in\cl{\Sigma}$ é aceite pelo AFD $A$ se, e só se $\hat{\delta}\del{q_I, p}\in F$. Se $\hat{\delta}\del{q_I, p} \not\in F$ então $p$ é rejeitada.

Linguagens Reconhecidas pelos AFD

É altura de começar a fazer a ligação entre as linguagens regulares e os AFD.

Linguagem Reconhecida por um AFD. Seja $A = \del{Q, \Sigma, \delta, q_I, F}$ um AFD.

A linguagem reconhecida (ou aceite) por $A$ é $$L\at{A} = \set{p \in \cl{\Sigma}\st \hat{\delta}\at{q_I, p} \in F}.$$

Dois AFD são equivalentes se aceitam a mesma linguagem.

Tal como com as expressões regulares, a definição de “equivalência” depende das linguagens associadas.

Conclusão

Nesta secção definiu-se um modelo de “computação” simples, os autómatos finitos deterministas e associou-se uma linguagem a cada AFD.

A intenção aqui é obter-se um modelo de computação das linguagens regulares. Portanto é preciso responder afirmativamente a estas duas questões:

1. Qualquer linguagem regular é aceite por um AFD?
2. Qualquer linguagem aceite por um AFD é regular?

Estas duas questões são tratadas na próxima secção.