Autómatos Finitos Deterministas

Um modelo computacional simples, com memória limitada.

• Autómatos Finitos Deterministas
  • Introdução
  • Autómato Finito Determinista
    • Configuração, Computação, Aceitação
  • Diagramas dos Autómatos Finitos Deterministas
  • Transição Estendida
  • Linguagens Reconhecidas pelos AFD
  • Conclusão

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 $\left(Q,\Sigma ,\delta ,q_I,F\right)$ 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=\left(\left\{q_0,q_1,q_2,q_3\right\},\left\{0,1\right\},\delta ,q_0,\left\{q_1,q_2\right\}\right)$ em que a transição $\delta$ é definida pela seguinte tabela: $$\begin{array}{ccc}\delta & 0& 1\\ q_0& q_1& q_2\\ q_1& q_2& q_3\\ q_2& q_2& q_2\\ q_3& q_3& q_3\end{array}$$

• Os estados de controlo são os elementos de $Q=\left\{q_0,q_1,q_2,q_3\right\}$.
• O alfabeto de entrada é $\Sigma =\left\{0,1\right\}$.
• A transição é a função $\delta (q,s)=q^{\prime }$ em que $q^{\prime }$ 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=\left\{q_1,q_2\right\}$.

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: $$\left\{\left(i,a,j\right):j=\delta \left(i,a\right),i\in Q,a\in \Sigma \right\}.$$

A transição acima como um conjunto de triplos fica: $$\left\{\left(q_0,0,q_1\right),\left(q_0,1,q_2\right),\left(q_1,0,q_2\right),\left(q_1,1,q_3\right),\dots \right\}$$

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

A computação da palavra $p=000$ por este autómato é a sequência $$q_0\stackrel{0}{⊢}{q}_1\stackrel{0}{⊢}{q}_2\stackrel{0}{⊢}{q}_2\in F.$$

A notação $q\stackrel{a}{⊢}{q}^{\prime }$ indica que o autómato passa do estado $q$ para $q^{\prime }$ 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=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFD.

Uma configuração de $A$ é um par $\left(q,s\right)\in Q\times {\Sigma }^{\ast }$ onde $q$ é o estado atual e $s$ é o sufixo restante.

A computação da palavra $p=a_1{a}_2\dots a_n\in {\Sigma }^{\ast }$ pelo AFD $A$ é a sequência de configurações $$\left(q_0,a_1{a}_2\dots a_n\right){⊢}_A\left(q_1,a_2\dots a_n\right){⊢}_A\cdots {⊢}_A\left(q_n,\lambda \right)$$ em que:

• base (configuração inicial) $q_0=q_I$.
• passo (processamento do símbolo ativo) $q_i=\delta \left(q_{i-1},a_i\right),i\ge 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 é $\left(q_0,\underline{0}00\right)$. O "símbolo ativo" está sublinhado.
2. Aplicando o passo obtém-se a configuração $\left(q_1,\underline{0}0\right)$ porque $q_1=\delta \left(q_0,0\right)$.
3. O passo é repetidamente aplicado, consumindo o símbolo ativo de cada vez, até que o sufixo restante é $\lambda$:
   1. $\left(q_1,\underline{0}0\right)⊢\left(q_2,\underline{0}\right)$.
   2. $\left(q_2,\underline{0}\right)⊢\left(q_2,\lambda \right)$.

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

$$\begin{array}{cl}q& s\\ q_0& 000\\ q_1& 00\\ q_2& 0\\ q_2& \lambda \end{array}$$ ou de forma ainda mais compacta: $$\begin{array}{l}{q}_{0}000\\ q_{1}00\\ q_{2}0\\ q_2\lambda \end{array}$$ ou ainda $$q_0\stackrel{000}{⊢}{q}_1\stackrel{00}{⊢}{q}_2\stackrel{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\stackrel{010}{⊢}{q}_1\stackrel{10}{⊢}{q}_3\stackrel{0}{⊢}{q}_3\notin F.$$

Neste caso a computação termina no estado $q_3\notin 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=\left(Q,\Sigma ,\delta ,q_I,F\right)$ 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^{\prime }=\delta \left(q,a\right)$ 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 {\Sigma }^{\ast }\to Q$.

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

• base - palavra vazia $\hat{\delta }\left(q,\lambda \right)=q$.
• base - símbolos Para cada $a\in \Sigma ,\hat{\delta }\left(q,a\right)=\delta \left(q,a\right)$.
• passo Se $p\in {\Sigma }^{\ast },a\in \Sigma$ então $\hat{\delta }\left(q,pa\right)=\delta \left(\hat{\delta }\left(q,p\right),a\right)$.

Intuitivamente, $\hat{\delta }\left(q,p\right)$ é 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{array}{rl}\hat{\delta }\left(q_0,000\right)& =\delta \left(\hat{\delta }\left(q_0,00\right),0\right)\\ & =\delta \left(\delta \left(\hat{\delta }\left(q_0,0\right),0\right),0\right)\\ & =\delta \left(\delta \left(\delta \left(q_0,0\right),0\right),0\right)\\ & =\delta \left(\delta \left(q_1,0\right),0\right)\\ & =\delta \left(q_2,0\right)\\ & =q_2\end{array}$$ e $$\begin{array}{rl}\hat{\delta }\left(q_0,010\right)& =\delta \left(\hat{\delta }\left(q_0,01\right),0\right)\\ & =\delta \left(\delta \left(\hat{\delta }\left(q_0,0\right),1\right),0\right)\\ & =\delta \left(\delta \left(\delta \left(q_0,0\right),1\right),0\right)\\ & =\delta \left(\delta \left(q_1,1\right),0\right)\\ & =\delta \left(q_3,0\right)\\ & =q_3\end{array}$$

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

1. Computação $\hat{\delta }\left(q,p\right)=q^{\prime }\iff \left(q,p\right){⊢}_A^{\ast }\left(q^{\prime },\lambda \right)$.
2. Aceitação $p\in {\Sigma }^{\ast }$ é aceite pelo AFD $A$ se, e só se $\hat{\delta }\left(q_I,p\right)\in F$. Se $\hat{\delta }\left(q_I,p\right)\notin 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=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFD.

A linguagem reconhecida (ou aceite) por $A$ é $$L\left(A\right)=\left\{p\in {\Sigma }^{\ast }:\hat{\delta }\left(q_I,p\right)\in F\right\}.$$

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.