Converter expressões e autómatos

A expressão $(a+b)^*a$ descreve palavras terminadas em $a$. Uma máquina equivalente tem de aceitar $a$ e $ba$, mas rejeitar $\varepsilon$ e $ab$. A construção de Thompson permite obter essa máquina seguindo a estrutura da expressão.

No sentido inverso, a eliminação de estados resume percursos por expressões, usando a precedência das expressões e o fecho-ε.

Expressão para ε-NFA: Thompson

A construção de Thompson associa a cada expressão um fragmento com uma entrada e uma saída. A entrada não tem arestas a chegar de dentro do fragmento e a saída não tem arestas a sair dentro dele. A saída será o único estado final quando o fragmento estiver completo.

Os casos básicos são:

• $a$: dois estados ligados por uma aresta $a$;
• $\varepsilon$: dois estados ligados por uma aresta vazia;
• $\emptyset$: dois estados sem ligação, porque não há palavra que deva passar entre eles.

As composições ligam esses fragmentos. Em cada caso, um percurso completo lê primeiro uma palavra de $L(E)$ e depois uma de $L(F)$, ou escolhe um dos ramos, ou repete o fragmento:

• Para $EF$, liga a saída de $E$ à entrada de $F$ por $\varepsilon$.
• Para $E+F$, acrescenta entrada e saída novas. Da entrada saem duas arestas vazias para as entradas dos fragmentos. As duas saídas chegam à saída nova por arestas vazias.
• Para $E^*$, acrescenta entrada e saída novas e quatro arestas vazias: da entrada nova para o fragmento e para a saída nova; da saída do fragmento para a sua entrada e para a saída nova. O caminho direto aceita zero repetições.

Fragmentos separados de Thompson

Para $a^*$: entrada $s$, saída $f$, fragmento interior $p \xrightarrow{a} q$, com $s \xrightarrow{\varepsilon} p$, $s \xrightarrow{\varepsilon} f$, $q \xrightarrow{\varepsilon} p$ e $q \xrightarrow{\varepsilon} f$. O caminho direto $s \to f$ aceita $\varepsilon$; o ciclo aceita $a$, $aa$ e continua.

Para $ab$: fragmento de $a$ com $p \xrightarrow{a} q$, fragmento de $b$ com $r \xrightarrow{b} t$, mais $q \xrightarrow{\varepsilon} r$. Um percurso completo lê primeiro $a$ e depois $b$. Sem essa aresta intermédia, nenhum percurso vai da entrada do primeiro fragmento à saída do segundo. A concatenação não aceita palavra alguma.

Para $a+b$: entrada nova $s$ com $s \xrightarrow{\varepsilon} p$ e $s \xrightarrow{\varepsilon} r$; saídas $q,t$ com $q \xrightarrow{\varepsilon} f$ e $t \xrightarrow{\varepsilon} f$. Cada percurso escolhe um ramo e só um.

Exemplo com união, estrela e concatenação

Para $(a+b)^*a$, constrói primeiro $a+b$, depois aplica estrela, depois concatena o último $a$. A construção, sem simplificações, fica:

Para aceitar $ba$, atravessa o ramo $b$ uma vez, sai da estrela e lê o $a$ final. Para aceitar $a$, salta a estrela. A palavra vazia é rejeitada porque a última aresta $a$ é obrigatória.

O desenho não precisa de ser o menor autómato. A vantagem é o procedimento sistemático e a prova por indução estrutural: os casos básicos reconhecem as linguagens certas e cada composição preserva a operação pretendida. A determinização pode vir depois.

Derivadas de expressões

Depois de ler o primeiro $a$ de uma palavra que deve terminar em $ab$, o que ainda falta ler? A expressão pode guardar esse conjunto de continuações. A derivada $D_a(E)$ descreve

$$L(D_a(E))=\{w\mid aw\in L(E)\}.$$

Não remove um $a$ em qualquer posição: trata a letra que acabou de ser lida no início. Dizemos que $E$ é anulável quando $\varepsilon\in L(E)$; uma expressão anulável pode aceitar sem ler outra letra.

As bases são $D_a(\emptyset)=D_a(\varepsilon)=\emptyset$. Para uma expressão que é só um símbolo, a derivada dá $\varepsilon$ se esse símbolo for $a$, e $\emptyset$ caso contrário. As operações seguem a origem da primeira letra:

$$D_a(E+F)=D_a(E)+D_a(F),\qquad D_a(E^*)=D_a(E)E^*.$$

Na concatenação, há duas possibilidades. A letra pode vir de uma palavra não vazia de $E$. Se $E$ aceitar $\varepsilon$, pode também vir diretamente de $F$:

$$D_a(EF)= \begin{cases} D_a(E)F+D_a(F),&\varepsilon\in L(E),\\ D_a(E)F,&\varepsilon\notin L(E). \end{cases}$$

Esta segunda parcela é necessária. Em $E=a^*$ e $F=b$, ler $b$ pode saltar a estrela e consumir a letra de $F$; a derivada tem de aceitar $\varepsilon$.

Um DFA cujos estados são expressões

Usa $R=(a+b)^*ab$. Como a estrela é anulável, $D_a(R)=R+b$ e $D_b(R)=R$. Em $R+b$, a letra $b$ pode concluir o sufixo: $D_b(R+b)=R+\varepsilon$.

Os três estados alcançáveis são as expressões seguintes, simplificadas pelas leis de união. Um estado é final exatamente quando a sua expressão é anulável:

Estado e expressão	$a$	$b$	Final?
$A=R$, inicial	$B$	$A$	Não
$B=R+b$	$B$	$C$	Não
$C=R+\varepsilon$	$B$	$A$	Sim

Para $ab$, a leitura passa por $R$, $R+b$, $R+\varepsilon$ e aceita. Para $aba$, a última letra deixa $R+b$, que não é anulável, e rejeita. Não se apaga a parcela $R$: ela permite que o prefixo continue enquanto tentamos completar o sufixo.

Depois de qualquer prefixo $x$, o estado descreve exatamente $\{w\mid xw\in L(R)\}$. Cada derivada preserva esse significado ao ler a próxima letra. No fim, aceitar $\varepsilon$ na expressão restante equivale a a palavra lida pertencer à linguagem original. Esta é a construção por derivadas de Brzozowski, uma alternativa a Thompson seguido de determinização. Expressões com textos diferentes podem representar o mesmo estado por linguagem; não as distingas apenas pela escrita.

Autómato para expressão: eliminação de estados

Permite agora que uma aresta tenha uma expressão regular, não apenas uma letra; chama autómato generalizado a esta representação. Uma aresta ausente tem rótulo $\emptyset$, e várias arestas paralelas juntam-se por união.

Prepara a máquina acrescentando uma entrada nova $s$ e uma saída nova $f$. Liga $s$ ao antigo início por $\varepsilon$ e cada antigo final a $f$ por $\varepsilon$. Só $f$ fica final, o que resolve também o caso em que o estado inicial era final.

Quando eliminas o estado $k$, atualiza cada ligação entre estados que ficam:

$$R'_{ij}=R_{ij}+R_{ik}(R_{kk})^*R_{kj}.$$

A primeira parte conserva os caminhos que não passam por $k$. A segunda entra em $k$, repete o ciclo zero ou mais vezes e sai para $j$. Usa os rótulos anteriores à eliminação em toda essa ronda, antes de remover $k$.

Exemplo com um ciclo

Considera um estado inicial $p$ com ciclo $a$, uma aresta $p\xrightarrow{b}q$ e um estado final $q$ com ciclo $c$:

Depois de acrescentar $s,f$, elimina $p$. A nova aresta de $s$ para $q$ tem rótulo

$$\emptyset+\varepsilon a^*b\equiv a^*b.$$

Elimina $q$ e obténs

$$R_{sf}=\emptyset+(a^*b)c^*\varepsilon\equiv a^*bc^*.$$

Há exatamente um $b$, antes dele só $a$ e depois só $c$. A ordem de eliminação pode produzir expressões diferentes, mas equivalentes. Eliminar primeiro estados com poucas ligações evita expressões grandes; não altera a linguagem.

Eliminação completa com retorno e dois finais

Considera estados $p$ inicial e $q,r$ finais, com $p \xrightarrow{a} p$, $p \xrightarrow{b} q$, $q \xrightarrow{a} p$, $q \xrightarrow{b} r$ e $r \xrightarrow{a,b} r$. Acrescenta entrada $s \xrightarrow{\varepsilon} p$ e saída $f$, com $q \xrightarrow{\varepsilon} f$ e $r \xrightarrow{\varepsilon} f$. Há um ciclo com retorno $p \leftrightarrow q$ e um final $r$ que absorve tudo.

Elimina por rondas, usando sempre os rótulos anteriores à ronda. Começa por $r$, que só tem saídas para $f$ além dos seus ciclos:

Ronda	Estado retirado	Rótulos novos
1	$r$	$R_{qf}$ ganha $b(a+b)^*$: sair de $q$ para $r$ e ficar lá um tempo arbitrário antes de terminar. As restantes arestas mantêm-se.
2	$p$	$R_{sq}=a^*b$ e $R_{qq}=aa^*b$: chegar pela primeira vez a $q$, ou regressar a $q$ através de $p$.
3	$q$	$R_{sf}=a^*b(aa^*b)^*(\varepsilon+b(a+b)^*)$.

Depois de retirar $r$, temos $R_{qf}=\varepsilon+b(a+b)^*$. O $\varepsilon$ conserva a possibilidade de terminar em $q$, sem passar por $r$.

A primeira parte da expressão final chega pela primeira vez a $q$. A estrela permite regressar a $q$ através de $p$; o último fator permite terminar ali ou entrar no final absorvente $r$. $b$, $bb$ e $bab$ são aceites. $\varepsilon$, $a$ e $aba$ são rejeitadas, pois nenhuma termina num final. Estes testes conferem a conta; a fórmula de eliminação justifica a equivalência para todas as palavras.

Caminhos com estados intermédios limitados

Ver a recorrência alternativa com estados limitados

Uma alternativa calcula $R_{ij}^{(k)}$, a expressão dos caminhos de $i$ para $j$ cujos estados intermédios estão entre os primeiros $k$ estados. A recorrência é:

$$R_{ij}^{(k)}=R_{ij}^{(k-1)}+ R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^*R_{kj}^{(k-1)}.$$

Na base $k=0$, junta as arestas diretas de $i$ para $j$ e inclui $\varepsilon$ quando $i=j$, porque existe um caminho com zero passos de um estado para si mesmo. No fim, junta $R_{q_0f}^{(n)}$ para todos os finais $f$. O mesmo raciocínio de entrar, repetir e sair justifica a recorrência.

Equivalência de representações

Uma linguagem é regular se pode ser descrita por uma expressão regular, um DFA, um NFA ou um ε-NFA. As construções anteriores, com a construção de subconjuntos, provam a equivalência.

Para complementar uma expressão $E$, não há uma regra que troque cada operador por outro e resolva todos os casos. Converte $E$ para um autómato, determiniza, completa, troca os finais e converte novamente para expressão. Para provar que duas expressões são equivalentes, podes comparar os DFA em vez de tentar simplificações algébricas à mão.