# Converter expressões e autómatos

Construção de Thompson, eliminação de estados e equivalência entre descrições regulares.

Página: https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/

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](https://resumos.rgo.pt/cadeiras/tc/linguagens-expressoes/#express%C3%B5es-regulares) e o [fecho-ε](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#transi%C3%A7%C3%B5es-%CE%B5-e-fecho-%CE%B5).

## 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:

![Construção de Thompson para a ou b, repetidos zero ou mais vezes, seguidos de a. A entrada s pode saltar a repetição; o último a é obrigatório antes de f.](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/figura-1.svg)

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](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#determinizar-com-fechos) 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$:

![Autómato com ciclo a no início p, transição b para o final q e ciclo c em q.](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/figura-2.svg)

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](https://resumos.rgo.pt/cadeiras/tc/limites-regulares/#teste-de-equival%C3%AAncia) em vez de tentar simplificações algébricas à mão.

## Exercícios

Os problemas são originais, salvo as adaptações identificadas no enunciado.

Calcular o novo rótulo

Ao eliminar k, os rótulos existentes são $R_{ij}=d$, $R_{ik}=a$, $R_{kk}=b$ e $R_{kj}=c$. Qual fica o rótulo de i para j? Descreve a linguagem desse rótulo.

Pista

Há caminhos que não passam por k e caminhos que passam.

Mais uma pista

Os que passam por k leem a, repetem o ciclo b e leem c.

Solução

O novo rótulo é $d+ab^*c$. Aceita a palavra d ou uma palavra que começa em a, segue com zero ou mais b e termina em c. Inclui ac, abc e abbc.

Confere a tua resposta:

*   Conserva a aresta direta d.
*   Inclui uma entrada por a, zero ou mais b e saída por c.
*   Junta os dois caminhos por união, não concatenação.

Erros frequentes

Não percas a ligação direta d. Não exijas pelo menos um b: a estrela permite atravessar k sem dar uma volta ao ciclo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#aut%C3%B3mato-para-express%C3%A3o-elimina%C3%A7%C3%A3o-de-estados)

Escolher o caminho de conversão

Queres uma expressão regular para o complemento de $(ab)^*$ sobre $\{a,b\}$. Descreve um procedimento que termina e explica o que acontece a $\varepsilon$ e a $aba$.

Pista

Usa a equivalência entre expressões e máquinas, em vez de trocar operadores à mão.

Mais uma pista

No DFA, cada palavra tem um só estado final da computação.

Solução

Constrói o ε-NFA por Thompson, determiniza por subconjuntos, inclui o poço para ter transições totais e troca finais com não finais. Converte o DFA resultante em expressão por eliminação de estados. Como $\varepsilon\in(ab)^*$, é rejeitada pelo complemento. Como aba não consiste em blocos completos ab, é aceite pelo complemento.

Confere a tua resposta:

*   Converte a expressão num ε-NFA e calcula o DFA completo.
*   Troca os finais apenas no DFA.
*   Usa eliminação de estados se for exigida uma expressão para o complemento.

Erros frequentes

Não tomes $(a+b)^*-(ab)^*$ como expressão construída pelos operadores básicos: a diferença tem de ser realizada por uma construção.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#equival%C3%AAncia-de-representa%C3%A7%C3%B5es)

Construir os fragmentos

Aplica Thompson a $a^*+b$. Dá a lista de arestas, o início e o único final, sem simplificar os fragmentos. Justifica $\varepsilon$, $aa$, $b$ e $ab$.

Pista

Faz primeiro os dois ramos a estrela e b; só depois liga a união.

Mais uma pista

Usa $a_0\xrightarrow{a}a_1$ e $b_0\xrightarrow{b}b_1$. A estrela precisa de dois estados novos.

Solução

Começa pelas arestas $a_0\xrightarrow{a}a_1$ e $b_0\xrightarrow{b}b_1$. Para a estrela, acrescenta $u,v$ e as arestas vazias $u\to a_0$, $u\to v$, $a_1\to a_0$, $a_1\to v$. Para a união, acrescenta início $s$, final $f$ e as arestas vazias $s\to u$, $s\to b_0$, $v\to f$, $b_1\to f$. São oito estados e só $f$ é final.

$\varepsilon$ passa por $s,u,v,f$ sem ler letras. $aa$ percorre a aresta de $a$ duas vezes, repetindo pelo ciclo vazio. $b$ escolhe o outro ramo. $ab$ não é aceite: nenhum percurso pode ler parte no ramo $a^*$ e depois mudar para o ramo $b$.

Confere a tua resposta:

*   Constrói o fragmento de a e as quatro arestas vazias da estrela.
*   Acrescenta entradas e saídas novas para a união.
*   Mostra que cada percurso da união escolhe um ramo, sem os concatenar.

Erros frequentes

Não ligues a saída da estrela à entrada de b: isso construiria concatenação. Não marques as saídas internas como finais da união.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#express%C3%A3o-para-%CE%B5-nfa-thompson)

Eliminação com retorno

Sobre $\{a,b\}$, um DFA tem início $p$, finais $q,r$ e transições $p\xrightarrow{a}p$, $p\xrightarrow{b}q$, $q\xrightarrow{a}p$, $q\xrightarrow{b}r$, $r\xrightarrow{a,b}r$. Converte-o numa expressão regular, eliminando pela ordem $r,p,q$. Mostra os rótulos novos de cada ronda e testa $b,bb,bab,aba$.

Pista

Depois de retirar p, pergunta que palavra faz uma volta de q até q.

Solução

Acrescenta início $s\xrightarrow{\varepsilon}p$ e saída $f$, com $q,r\xrightarrow{\varepsilon}f$. Só $f$ fica final. Ao retirar $r$, $R_{qf}=\varepsilon+b(a+b)^*$. Ao retirar $p$, $R_{sq}=a^*b$ e $R_{qq}=aa^*b$; $R_{qf}$ mantém-se. Retirar $q$ dá

$$
a^*b(aa^*b)^*(\varepsilon+b(a+b)^*).
$$

$b$ chega a $q$ e termina; $bb$ chega a $r$; $bab$ regressa de $q$ a $p$ e volta a $q$. Todas são aceites pela expressão e pelo DFA. $aba$ termina em $p$ e é rejeitada. Os rótulos de uma ronda usam todos os valores anteriores à eliminação do estado dessa ronda.

Confere a tua resposta:

*   Preparei início e final novos.
*   Mantive ε na saída de q e calculei o ciclo aa\*b.
*   Obtive a expressão e conferi as quatro palavras.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#elimina%C3%A7%C3%A3o-completa-com-retorno-e-dois-finais)

Uma continuação que pode terminar agora

Usa derivadas para construir um DFA completo equivalente a $R=(a+b)^*aba$. Dá as expressões dos estados alcançáveis, a tabela e os finais. Segue $aba$, $ababa$ e $abab$. Explica por que não podes omitir a derivada do fator $aba$ ao calcular $D_a(R)$. Este problema próprio usa o método de conversão pedido na questão 3 do teste de 24/3/2023, com outra expressão.

Pista

A estrela pode gerar ε. Depois de ler a, também existe uma tentativa de completar o sufixo ba.

Solução

A primeira derivada é $D_a(R)=R+ba$, porque $(a+b)^*$ pode ler o $a$ ou desaparecer antes do fator $aba$. Por $b$, fica $D_b(R)=R$. Repetindo a derivação, surgem quatro expressões:

| Estado | $a$ | $b$ | Final? |
| --- | --- | --- | --- |
| $A=R$, inicial | $B$ | $A$ | Não |
| $B=R+ba$ | $B$ | $C$ | Não |
| $C=R+a$ | $D$ | $A$ | Não |
| $D=R+ba+\varepsilon$ | $B$ | $C$ | Sim |

Só $D$ aceita ε. $aba$ segue $A,B,C,D$; $ababa$ segue $A,B,C,D,C,D$. Ambas aceitam. $abab$ segue $A,B,C,D,C$ e rejeita, embora tenha passado por um final.

Depois do prefixo lido, cada expressão descreve todas as continuações que completam uma palavra terminada em aba. A parcela R conserva as tentativas que ainda começam mais à frente. Se ignorássemos a anulabilidade da estrela, a derivação deixaria sempre R, nunca apareceria ε e até aba seria rejeitada.

Confere a tua resposta:

*   Mantive a parcela R nas derivadas e a continuação ba depois de a.
*   Obtive quatro estados alcançáveis e marquei só R+ba+ε como final.
*   Aceitei aba e ababa e rejeitei abab, conferindo o invariante de continuações.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#derivadas-de-express%C3%B5es)