Minimização e Composição de AFD

Operações com autómatos.

• Minimização e Composição de AFD
  • Introdução
  • Minimização de AFD
    • Estados Indistintos
    • Construção do Autómato Mínimo por Tabelas de Transição
    • Construção do Autómato Mínimo por Diagramas
  • Composição
    • Paralelismo
  • Conclusão

Introdução

Nas secções anteriores ficou provado que os AFD, AFND e as ER são equivalentes no sentido em que todos definem exatamente a classe das Linguagens Regulares.

Essa demonstração usa algoritmos para:

• Converter uma ER num AFND (Construção de Thompson).
• Converter um AFND numa ER (Algoritmo de Kleene).
• Simular um AFND por um AFD (Teorema da Simulação).

Comparando os AFD com os AFND:

Em termos de eficiência "absoluta" nenhum dos modelos (AFD e AFND) é superior. Mas enquanto não há nada a fazer em relação às computações não deterministas, em certos casos é possível reduzir o número de estados de um AFD.

Também interessa definir operações com autómatos que permitam acompanhar as operações das ER (união, concatenação, iteração) e também explorar outras possibilidades como a negação, a interseção e o processamento paralelo.

Minimização de AFD

Seja $L$ a linguagem das palavras binárias (sobre $\left\{a,b\right\}$) cujo quinto símbolo a contar do fim é $a$. Esta linguagem é definida pela ER ${\left(a\cup b\right)}^{\ast }a(a\cup b)(a\cup b)(a\cup b)(a\cup b)$ a que corresponde o diagrama e AFND seguinte:

AFND para ${\left(a\cup b\right)}^{\ast }a(a\cup b)(a\cup b)(a\cup b)(a\cup b)$

Exercício: A aplicação direta do teorema da simulação determinista a este AFND produz um autómato com $32$ estados de controlo.

A simulação de um AFND com $n$ estados de controlo pode produzir até $2^n$ estados no autómato determinista equivalente (exercício: porquê?).

Estados Indistintos

Dois AFD são equivalentes se aceitam a mesma linguagem. Por exemplo, para a linguagem $a^{\ast }$:

Autómato $A$	Autómato $B$

No Autómato $B$ os estados $I$ e $1$ são indistintos no seguinte sentido: Qualquer palavra processada a partir do estado $I$ é aceite SSE também for aceite se processada a partir do estado $1$.

Por exemplo, se $p=\lambda$ e o autómato estiver no estado $I$ então $p$ é "aceite". Também é "aceite" se o autómato estiver no estado $1$. Por outro lado $p=b$ é rejeitada quer o autómato esteja no estado $I$ quer no $1$.

Portanto, tanto $I$ como $1$ definem sempre os mesmos resultados em termos de aceitação/rejeição de palavras. Formalmente:

Estados Indistintos. Sejam $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFD e $i,j\in Q$ dois estados. Então $i$ é indistinto de $j$ se, para cada palavra $p\in {\Sigma }^{\ast }$, $$\hat{\delta }\left(i,p\right)\in F\iff \hat{\delta }\left(j,p\right)\in F.$$ Em particular, se $i\in F$ e $j\in Q\setminus F$ não são indistintos.

Agrupando estados indistintos obtém-se um novo AFD com o número mínimo de estados para aquela linguagem regular, isto é, um Autómato Mínimo. Antes da respetiva definição formal é conveniente descrever um algoritmo para particionar os estados indistintos.

O objetivo é particionar o conjunto de estados em grupos de forma que dois estados estão no mesmo grupos se e só se são indistintos.

Partição dos Estados Indistintos. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFD:

1. Iniciar a partição $P=\left\{Q\setminus F,F\right\}$.
2. Enquanto existirem grupos $X,Y\in P$ com $i,j\in X$ e $a\in \Sigma$ tais que $\delta \left(i,a\right)\in Y,\delta \left(j,a\right)\notin Y$ ($X$ é inconsistente):
   1. Retirar $X$ da partição $P$: $P\to P\setminus \left\{X\right\}$.
   2. Acrescentar os estados de $X$ concordantes com $i$ em $a$: $P\to P\cup \left\{k\in X:\delta \left(k,a\right)\in Y\right\}$.
   3. Acrescentar os estados de $X$ discordantes de $i$ em $a$: $P\to P\cup \left\{k\in X:\delta \left(k,a\right)\notin Y\right\}$.

Os passos deste ciclo refinam $X$ de forma a eliminar discordâncias de $i\in X$ sobre $a\in \Sigma$. O resultado é que a partição $P$ troca o grupo inconsistente $X$ por dois grupos mais pequenos mas "menos" inconsistentes, isto é, onde os estados estão "mais próximos" de serem indistintos.

A partição final é formada apenas por grupos consistentes, isto é, em que todos os estados são indistintos (no limite esses grupos têm apenas um estado). Os grupos dessa partição são os estados do AFD mínimo equivalente ao AFD inicial.

Autómato Mínimo. Sejam $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFD e $P$ a partição dos estados indistintos.

Para cada grupo $X\in P$ e cada $a\in \Sigma$ $${\delta }^{\prime }\left(X,a\right)=Y$$ em que $Y\in P$ é o grupo que contém $\delta \left(i,a\right)$ com $i\in X$.

O AFD Mínimo (ou reduzido) equivalente a $A$ é $A^{\prime }=\left(P,\Sigma ,{\delta }^{\prime },q_I^{\prime },F^{\prime }\right)$ em que:

1. O estado inicial, $q_I^{\prime }$, é o grupo de $P$ que contém o estado inicial $q_I$ de $A$.
2. Os estados finais, $F^{\prime }$, são os grupos de $P$ que estão contidos em $F$. Isto é

$$F^{\prime }=\left\{X\in P:X\subseteq F\right\}.$$

A construção do autómato mínimo a partir da definição está sujeita a erros, pelo que são ilustrados de seguida dois métodos com vista a sistematizar e facilitar esse processo.

Dado o AFD $A$ pela seguinte tabela:

$$\begin{array}{rcc}\delta & a& b\\ i0& 1& 4\\ f1& 4& 2\\ 2& 3& 5\\ f3& 5& 2\\ 4& 5& 5\\ 5& 4& 5\end{array}$$

Construção do Autómato Mínimo por Tabelas de Transição

Iniciar grupos, detetar e assinalar inconsistências:

$$\begin{array}{rllrllrll}& \delta & & & a& & & b& \\ 0& \boxed{A}& & 1& B& & 4& A& \\ f1& B& & 4& A& & 2& A& \\ 2& \boxed{A}& & 3& B& & 5& A& \\ f3& B& & 5& A& & 2& A& \\ 4& \boxed{A}& & 5& A& & 5& A& \\ 5& \boxed{A}& & 4& A& & 5& A& \end{array}$$

Separar inconsistências, detetar e assinalar novas inconsistências:

$$\begin{array}{rllrllrll}& \delta & & & a& & & b& \\ 0& A& A& 1& B& B& 4& A& C\\ f1& B& B& 4& A& C& 2& A& A\\ 2& A& A& 3& B& B& 5& A& C\\ f3& B& B& 5& A& C& 2& A& A\\ \boxed{4}& \xcancel{A}& C& 5& A& C& 5& A& C\\ \boxed{5}& \xcancel{A}& C& 4& A& C& 5& A& C\end{array}$$

Não existem mais inconsistências: Agrupar e escrever a tabela do AFD mínimo:

$$\begin{array}{rcc}\delta & a& b\\ q_I^{\prime }=A=\left\{0,2\right\}& B& C\\ fB=\left\{1,3\right\}& C& A\\ C=\left\{4,5\right\}& C& C\end{array}$$

Construção do Autómato Mínimo por Diagramas

O diagrama do AFD dado é:

AFD dado, com a partição inicial.
$0,2$ e $4,5$ discordam em $a$.
Todos os grupos são consistentes.
Diagrama do ADF Mínimo

Foram descritos dois métodos para reduzir o número de estados de um AFD (minimizar). Ambos produzem o mesmo resultado: um autómato determinista com o menor número possível de estados e que seja equivalente a um AFD dado.

Embora isto não resolva completamente o potencial aumento exponencial do número de estados na passagem de AFND para AFD, produz um resultado ótimo, no sentido em que não existe melhor (isto é, por vezes o ótimo pode ainda ser "mau").

Composição

A representação é importante. Intuitivamente, a numeração romana é equivalente à árabe no sentido que representam os mesmos números. Considere o Problema A: "Multiplicar DXXXIX por XVII" e o Problema B: "Multiplicar 89 por 17". Embora os problemas A e B sejam o mesmo, é muito mais simples resolver B porque a representação árabe dos números "é compatível com" a multiplicação, ao contrário da representação romana.

As ER são construídas a partir da base ($\varnothing ,\lambda ,a\in \Sigma$) usando operações bem definidas ($\cdot ,\cup ,{}^{\ast }$). Desta forma é possível decompor uma ER nas suas componentes, o que proporciona uma importante forma de análise com vista a explorar as suas propriedades.

Por outro lado, em geral, os autómatos "surgem" completamente definidos e é difícil relacionar um autómato com outro. Dado que as ER, os AFD e os AFND são "equivalentes", seria estranho que não fosse possível fazer também um estudo estruturado dos autómatos.

As operações com autómatos usam os Autómatos Bem Preparados pois estes têm uma forma adequada a serem "operados".

Começando pela concatenação, a ideia intuitiva para $AB$ é "correr" primeiro $A$ e continuar em $B$:

Concatenação de AFND. Sejam $A=\left(Q^A,\Sigma ,{\delta }^A,q_I^A,\left\{q_F^A\right\}\right)$ e $B=\left(Q^B,\Sigma ,{\delta }^B,q_I^B,\left\{q_F^B\right\}\right)$ dois AFND bem preparados sobre um alfabeto comum, $\Sigma$, e com os estados de controlo disjuntos, $Q^A\cap Q^B=\varnothing$.

Então, a concatenação de $A$ com $B$ é o AFND $AB$, definido por $\left(Q^A\cup Q^B,\Sigma ,{\delta }^{AB},q_I^A,\left\{q_F^B\right\}\right)$ em que

$${\delta }^{AB}={\delta }^A\cup {\delta }^B\cup \left\{\left(q_F^A,\lambda ,q_I^B\right)\right\}.$$

A linguagem reconhecida por $AB$ é a concatenação da linguagem reconhecida por $A$ com a linguagem reconhecida por $B$: $$L\left(AB\right)=L\left(A\right)L\left(B\right).$$

Exercício: $AB$ está bem preparado?

Por exemplo, se $A=\left(\left\{0,1\right\},\left\{a,b\right\},0,\left\{\left(0,a,1\right)\right\},\left\{1\right\}\right)$ e $B=\left(\left\{2,3\right\},\left\{a,b\right\},\left\{\left(2,b,3\right)\right\},2,\left\{3\right\}\right)$ (exercício: verifique que ambos são bem preparados e identifique as respetivas linguagens) então $$AB=\left(\left\{0,1,2,3\right\},\left\{a,b\right\},\left\{\left(0,a,1\right),\left(2,b,3\right),\left(1,\lambda ,2\right)\right\},1,\left\{3\right\}\right).$$

Exercício: Traduza este exemplo para diagramas. Qual é a linguagem aceite por $AB$?

A união de autómatos é semelhante à concatenação. Intuitivamente, o primeiro "passo" é decidir se "corre" $A$ ou $B$. A computação da união termina a seguir a terminar a computação do autómato "escolhido" no início.

União de AFND. Sejam $A=\left(Q^A,\Sigma ,{\delta }^A,q_I^A,\left\{q_F^A\right\}\right)$ e $B=\left(Q^B,\Sigma ,{\delta }^B,q_I^B,\left\{q_F^B\right\}\right)$ dois AFND bem preparados sobre um alfabeto comum, $\Sigma$, e com os estados de controlo disjuntos, $Q^A\cap Q^B=\varnothing$.

Então, a união de $A$ com $B$ é o AFND $A\cup B$, definido por $\left(Q^A\cup Q^B\cup \left\{q_I,q_F\right\},\Sigma ,{\delta }^{A\cup B},q_I,\left\{q_F\right\}\right)$ em que

$${\delta }^{A\cup B}={\delta }^A\cup {\delta }^B\cup \left\{\left(q_I,\lambda ,\left\{q_I^A,q_I^B\right\}\right),\left(q_F^A,\lambda ,\left\{q_F\right\}\right),\left(q_F^B,\lambda ,\left\{q_F\right\}\right)\right\}.$$

A linguagem reconhecida por $A\cup B$ é a união da linguagem reconhecida por $A$ com a linguagem reconhecida por $B$: $$L\left(A\cup B\right)=L\left(A\right)\cup L\left(B\right).$$

Continuando com os autómatos do exemplo acima: $$A\cup B=\left(\left\{0,1,2,3,I,F\right\},\left\{a,b\right\},\left\{\left(0,a,1\right),\left(2,b,3\right),\left(I,\lambda ,\left\{1,2\right\}\right),\left(1,\lambda ,F\right),\left(3,\lambda ,F\right)\right\},I,\left\{F\right\}\right).$$

Exercício: Desenhe o diagrama do autómato $A\cup B$ acima.

Também a iteração segue o mesmo padrão:

Iteração de AFND. Sejam $A=\left(Q^A,\Sigma ,{\delta }^A,q_I^A,\left\{q_F^A\right\}\right)$ um AFND bem preparado.

Então, a iteração de $A$ é o AFND $A^{\ast }$, definido por $\left(Q^A\cup \left\{q_I,q_F\right\},\Sigma ,{\delta }^{A^{\ast }},q_I,\left\{q_F\right\}\right)$ em que

$${\delta }^{A^{\ast }}={\delta }^A\cup \left\{\left(q_I,\lambda ,\left\{q_I^A,q_F\right\}\right),\left(q_F^A,\lambda ,\left\{q_I^A,q_F\right\}\right)\right\}.$$

A linguagem reconhecida por $A^{\ast }$ é o fecho da linguagem reconhecida por $A$: $$L\left(A^{\ast }\right)={L\left(A\right)}^{\ast }.$$

Exercício: Usando os exemplos acima, explicite as transições de $A^{\ast },A\cup B^{\ast },B^{\ast }B\cup A{B}^{\ast }$ e desenhe os respetivos diagramas.

A composição, união e iteração de AFND bem preparados são semelhantes em termos de requisitos e resultados. Para a negação e interseção é preciso sair desse padrão.

Intuitivamente, pensando em termos de autómatos deterministas, uma palavra é aceite se a computação termina num estado final e rejeitada se termina num estado não final. Portanto, basta trocar os estados finais com os não finais para se definir a linguagem complementar.

Quanto à interseção, uma vez definida a negação e a união, basta lembrar que para conjuntos, $A\cap B=\overline{\overline{A}\cup \overline{B}}$ e a mesma igualdade é válida para as linguagens regulares. Mas este processo é pouco prático.

Começando pela negação, é importante destacar que se aplica a autómatos deterministas ao contrário do que foi feito para a concatenação, união e iteração.

Negação de AFD. Sejam $A=\left(Q^A,\Sigma ,{\delta }^A,q_I^A,F^A\right)$ um AFD.

Então, a negação de $A$ é o AFND $\overline{A}$, definido por $\left(Q^A,\Sigma ,{\delta }^A,q_I^A,Q^A\setminus F^A\right)$.

A linguagem reconhecida por $\overline{A}$ é o complementar da linguagem reconhecida por $A$: $$L\left(\overline{A}\right)={\Sigma }^{\ast }\setminus L\left(A\right).$$

Um AFD e a sua negação
AFD para $a^{\ast }$
AFD para ${\Sigma }^{\ast }\setminus L\left(a^{\ast }\right)$

Paralelismo

É relativamente simples definir um autómato determinista que processa em paralelo outros dois (ou mais) autómatos também deterministas. Melhor, este método é suficientemente simples e geral para ter várias aplicações incluindo a união e interseção de AFD.

Em geral,

Autómato Paralelo. sejam $A=\left(Q^A,\Sigma ,{\delta }^A,q_I^A,F^A\right)$ e $B=\left(Q^B,\Sigma ,{\delta }^B,q_I^B,F^B\right)$ dois AFD sobre o mesmo alfabeto, $\Sigma$.

Seja $P_F^{A,B}=\left(Q^C,\Sigma ,{\delta }^C,q_I^C,F\right)$ o AFD tal que:

• Estados de Controlo: $Q^C=Q^A\times Q^B$, isto é: um estado de controlo de $C$ é um par ordenado com um estado de $A$ e um estado de $B$.
• Transição: ${\delta }^C\left(\left(i^A,i^B\right),a\right)=\left(j^A,j^B\right)$ em que $j^A={\delta }^A\left(i^A,a\right),j^B={\delta }^B\left(i^B,a\right)$, isto é: a transição de um estado é feira componente a componente.
• Estado Inicial: $q_I^C=\left(q_I^A,q_I^B\right)$, isto é: o estado inicial é o par de estados iniciais.
• Estados Finais: $F\subseteq Q^A\times Q^B$.

O conjunto dos estados finais fica como parâmetro porque proporciona uma grande flexibilidade aos autómatos paralelos. Por exemplo:

• União: Sejam $A,B$ dois AFD com estados finais $F^A,F^B$ respetivamente. Fazendo $F=\left\{\left(i^A,i^B\right):i^A\in F^A\vee i^B\in F^B\right\}$ tem-se $L\left(A\right)\cup L\left(B\right)=L\left(P_F^{A,B}\right)$. Note-se que uma palavra é aceite por $P_F^{A,B}$ se e só se é aceite por $A$ ou se é aceite por $B$.
• Interseção: Nas condições acima, seja $G=\left\{\left(i^A,i^B\right):i^A\in F^A\wedge i^B\in F^B\right\}$. Então $L\left(P_G^{A,B}\right)=L\left(A\right)\cap L\left(B\right)$. Note-se que uma palavra é aceite por $P_G^{A,B}$ se e só se é aceite por $A$ e por $B$.

Conclusão

Esta secção aprofundou o estudo dos AFD e AFND. Especificamente:

1. Mostram-se dois métodos para minimizar um dado AFD, de modo a obter-se um AFD equivalente com o menor número possível de estados.
2. Definiram-se as operações de concatenação, união e iteração de AFND, replicando as operações das ER.
3. Definiu-se a negação e composição paralela de AFD. Com o processamento paralelo de AFD ficou trivial definir as operações de união e a interseção de AFD.

O Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$ — continua em aberto. As expressões regulares e os autómatos finitos (deterministas e não deterministas) verificam duas das três condições fundamentais:

• São computáveis (existe um algoritmo que recebe uma palavra e num número finito de passos "responde" se essa palavra está ou não na linguagem pretendida) e eficientes (um AFD processa uma palavra com $n$ símbolos em exatamente $n$ passos).
• Além disso é (relativamente) simples encontrar ER, AFND, AFD equivalentes.

Resta verificar se as linguagens regulares são adequadas para definir as linguagens de programação.