Converter expressões e autómatos

Thompson: expressão para ε-NFA

Cada fragmento tem uma entrada e uma saída, e a saída será o único estado final quando o fragmento estiver completo.

Expressão	Construção
$a$, $\varepsilon$, $\emptyset$	Dois estados; aresta $a$, ε, ou nenhuma
$EF$	Liga a saída de $E$ à entrada de $F$ por ε; a saída antiga de $E$ passa a intermédia e só a saída de $F$ fica final
$E+F$	Uma entrada nova escolhe por ε e as saídas ligam por ε a uma saída nova
$E^*$	Uma entrada nova salta ou entra no fragmento; a saída do fragmento repete ou sai para uma saída nova

Na estrela, o caminho direto aceita $\varepsilon$. Em $(a+b)^*a$, as palavras $a$ e $ba$ são aceites e $\varepsilon$ e $ab$ são rejeitadas. O método é sistemático, não mínimo, e a correção segue por indução estrutural.

Eliminação: autómato para expressão

1. Acrescenta uma entrada nova $s$ com ε para o antigo início e uma saída nova $f$ com ε desde cada antigo final. Só $f$ fica final.
2. Cada aresta passa a ter uma expressão; arestas paralelas unem-se por união e a ausência vale $\emptyset$.
3. Para eliminar o estado $k$, atualiza cada par $i,j$ de estados sobreviventes com $i\ne k$ e $j\ne k$ por $R'_{ij}=R_{ij}+R_{ik}(R_{kk})^*R_{kj}$, sempre com os rótulos anteriores à ronda. Repete até só restarem $s$ e $f$.

Aqui: eliminar $p$ dá $s\to q$ com $a^*b$; eliminar $q$ dá $a^*bc^*$. A ordem muda o texto, não a linguagem.

Derivadas e equivalência

A derivada $D_a(E)$ é uma expressão que denota o quociente à esquerda pela letra $a$: a sua linguagem é $L(D_a(E))=\{w\mid aw\in L(E)\}$. Um estado-expressão é final exatamente quando a sua expressão aceita $\varepsilon$, isto é, quando é anulável.

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

Na concatenação, a letra pode vir de $E$ ou, quando $E$ aceita $\varepsilon$, diretamente de $F$:

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

• As expressões, os DFA, os NFA e os ε-NFA descrevem a mesma classe das linguagens regulares.
• Para complementar uma expressão, converte para autómato, determiniza, completa, troca os finais e converte de novo; não basta trocar operadores.
• Para comparar duas expressões, constrói o produto dos DFA; os testes com palavras revelam diferenças, mas só o algoritmo decide a equivalência.

Eliminação com retorno e derivadas.