Propriedades e limites das regulares

O DFA do sufixo $ab$ guarda três resumos possíveis. Mesmo que acrescentes estados, a memória continua finita. Para comparar contagens sem limite, como em $a^nb^n$, precisaremos de mostrar por que nenhum número finito de estados chega.

Primeiro usamos DFA completos para combinar condições e reduzir memória redundante; depois, o lema da repetição fornece uma condição necessária à regularidade.

Propriedades de fecho

Uma classe é fechada para uma operação quando aplicar essa operação a linguagens da classe dá sempre outra linguagem da mesma classe.

Para DFA completos $A,B$ sobre o mesmo alfabeto, o produto tem estados $(p,q)$, início $(p_0,q_0)$ e

$$\delta((p,q),a)=(\delta_A(p,a),\delta_B(q,a)).$$

Após ler $w$, cada componente é o estado que a respetiva máquina atingiria sozinha. A escolha dos finais determina a operação:

Linguagem	Quando $(p,q)$ é final
$L(A)\cap L(B)$	$p\in F_A$ e $q\in F_B$
$L(A)\cup L(B)$	$p\in F_A$ ou $q\in F_B$
$L(A)\setminus L(B)$	$p\in F_A$ e $q\notin F_B$
Diferença simétrica	Exatamente uma componente é final

Toda a linguagem finita é regular: cada palavra tem uma expressão, e uma união finita reúne todas. Para a linguagem vazia, usa $\emptyset$.

O complemento de uma regular resulta de trocar finais e não finais num DFA completo. Para concatenação e estrela, usa as construções por transições vazias ou as operações correspondentes em expressões regulares.

Para o reverso $L^R=\{w^R\mid w\in L\}$, inverte todas as arestas do autómato. O antigo início é o único final. Acrescenta um início novo com transições $\varepsilon$ para todos os antigos finais. Os percursos invertidos leem precisamente as palavras ao contrário.

As operações seguintes mudam um DFA existente em vez de combinar dois.

Quociente e derivada

Fixa uma letra $a$. O quociente à direita $L/a=\{w\mid wa\in L\}$ é regular. Mantém o DFA de $L$, mas torna final todo o estado $q$ com $\delta(q,a)\in F$. Agora aceita $w$ exatamente quando ler mais um $a$ levaria a um final.

A derivada à esquerda $a\backslash L=\{w\mid aw\in L\}$ também é regular. Mantém os finais e muda o início para $\delta(q_0,a)$. Já leste o primeiro $a$ antes de começar a simular $w$.

Intercalar palavras

A última construção deste grupo alterna letras de duas palavras em vez de as concatenar. Intercalar $x$ e $y$ conserva a ordem dos símbolos de cada palavra, mas pode alternar a sua origem. Por exemplo, intercalar $a$ e $bc$ dá $\{abc,bac,bca\}$.

Se $L_1,L_2$ são regulares, a linguagem de todas essas intercalações também é regular. Num NFA com estados $(p,q)$, cada letra pode atualizar a primeira componente ou a segunda, mantendo a outra. Cada ramo escolhe a que palavra pertence a letra; os finais exigem ambas as componentes finais. Isto difere do produto para interseção, onde a mesma letra atualiza as duas componentes.

Perguntas decidíveis

A linguagem pode ser infinita, mas a sua representação tem um grafo finito. Isso permite responder a várias perguntas com algoritmos que terminam.

Pergunta	Procedimento
$w\in L$?	Simula a máquina, mantendo um estado no DFA ou um conjunto no NFA.
$L=\emptyset$?	Procura um final alcançável a partir do início.
$L=\Sigma^*$?	Complementa o DFA completo e testa se o resultado é vazio.
$L$ é infinita?	Num DFA, procura um ciclo alcançável do início e do qual se alcance um final.
$L_1\subseteq L_2$?	Testa se $L_1\setminus L_2$ é vazia.

Um ciclo que nunca chega a um final não produz palavras aceites. Num ε-NFA, um ciclo só de arestas vazias não basta para produzir comprimentos ilimitados. Determinizar antes evita essa distinção.

Num DFA com $n$ estados, se uma palavra aceite tem comprimento pelo menos $n$, o seu percurso repete um estado. O ciclo repetido pode ser percorrido mais vezes, produzindo infinitas palavras. Inversamente, uma linguagem infinita tem comprimentos sem limite, porque há apenas finitas palavras de cada comprimento.

Teste de equivalência

Para comparar $A$ e $B$, procura no produto um estado alcançável em que exatamente uma componente seja final. Se não existir, nenhuma palavra distingue as máquinas, logo $L(A)=L(B)$.

Se existir, guarda o percurso desde o início: os rótulos formam uma palavra testemunha. Uma pesquisa em largura encontra uma das palavras distinguidoras mais curtas.

Por exemplo, o DFA para palavras que contêm $ab$ e o DFA para palavras que terminam em $ab$ não são equivalentes. A palavra $aba$ é aceite pelo primeiro e rejeitada pelo segundo. Comparar exemplos só prova a diferença quando encontra uma testemunha; não prova equivalência.

Minimização por preenchimento de tabela

Dois estados $p,q$ são equivalentes se todas as continuações $w$ dão a mesma resposta:

$$\forall w\in\Sigma^*,\quad \widehat\delta(p,w)\in F\iff\widehat\delta(q,w)\in F.$$

Remove primeiro os estados inacessíveis. Depois faz uma tabela dos pares de estados distintos:

1. Marca todo o par final/não final. A palavra $\varepsilon$ distingue esse par.
2. Marca $(p,q)$ se alguma letra $a$ leva a um par já marcado.
3. Repete até nenhuma marca nova surgir.
4. Junta os estados dos pares não marcados em classes. Cada classe torna-se um estado do DFA mínimo.

Se $w$ distingue os destinos de $p,q$ por $a$, então $aw$ distingue $p,q$. É por isso que as marcas propagam para trás. Os pares que continuam sem marca não têm qualquer continuação distinguidora.

Exemplo completo

Considera este DFA sobre $\{a,b\}$, com início $O$ e finais $C,D$:

Estado	$a$	$b$
$O$	$A$	$O$
$A$	$B$	$C$
$B$	$A$	$D$
$C$	$A$	$O$
$D$	$B$	$O$

Todos são alcançáveis, por $\varepsilon,a,aa,ab,aab$. Na base marca os seis pares entre $\{O,A,B\}$ e $\{C,D\}$.

Rondas da tabela e palavras distinguidoras

A ronda 0 marca os seis pares final/não final: $(O,C)$, $(O,D)$, $(A,C)$, $(A,D)$, $(B,C)$, $(B,D)$. A palavra $\varepsilon$ distingue cada um, porque só um dos estados é final.

Na ronda 1, o par $(O,A)$ marca-se porque por $b$ vai a $(O,C)$, já marcado; a palavra distinguidora é $b$. O par $(O,B)$ marca-se porque por $b$ vai a $(O,D)$; a palavra é também $b$. Os pares $(A,B)$ e $(C,D)$ não se marcam: por $a$, $(A,B)$ vai a $(B,A)$, o mesmo par; por $b$ vai a $(C,D)$. Por $a$, $(C,D)$ vai a $(A,B)$; por $b$ vai a $(O,O)$, um par de estados iguais.

Na ronda 2 não surge nenhuma marca nova, por isso o algoritmo para. As classes são $[O]$, $[AB]$ e $[CD]$. A palavra $\varepsilon$ distingue $[CD]$ das outras; a palavra $b$ distingue $[O]$ de $[AB]$, pois $[O]$ por $b$ fica fora do final e $[AB]$ por $b$ chega ao final.

A tabela abaixo regista a primeira ronda que distingue cada par. O ponto significa que nunca se marcou o par.

	$O$	$A$	$B$	$C$
$A$	1
$B$	1	·
$C$	0	0	0
$D$	0	0	0	·

Só $(A,B)$ e $(C,D)$ ficam sem marca. Fundindo-os, o início é $[O]$ e o único final é $[CD]$:

Classe	$a$	$b$
$[O]$	$[AB]$	$[O]$
$[AB]$	$[AB]$	$[CD]$
$[CD]$	$[AB]$	$[O]$

Reconheces o DFA para o sufixo $ab$. Ele é mínimo: $\varepsilon$ distingue o final dos outros dois, e $b$ distingue $[O]$ de $[AB]$. Um DFA mínimo completo é único a menos dos nomes dos estados.

O lema da repetição

Se $L$ é regular, existe um inteiro $p\ge1$ tal que toda a palavra $s\in L$ com $|s|\ge p$ admite uma decomposição $s=xyz$ com:

$$|y|\ge1,\qquad |xy|\le p,\qquad \forall i\ge0,\ xy^iz\in L.$$

Um DFA com $p$ estados percorre $p+1$ posições, incluindo a inicial, ao ler os primeiros $p$ símbolos. Algum estado repete. $x$ chega a esse estado, $y$ dá uma volta ao ciclo e $z$ segue até à aceitação. Repetir ou retirar o ciclo não muda o destino.

O ciclo da figura devolve a máquina ao mesmo estado. Por isso o sufixo $z$ continua a aceitar depois de zero, uma ou várias voltas.

O lema dá uma condição necessária, não um método para provar regularidade. Uma linguagem que satisfaz a condição não fica, só por isso, provada regular.

Provar que não é regular

Mostrar que um corte falha não prova nada. Em $L=\{(00)^n\mid n\ge0\}$, fixa um inteiro $p\ge2$ dado pelo lema e escolhe $s=0^{2p}$. O corte $x=\varepsilon$, $y=0$, $z=0^{2p-1}$ cumpre $|y|\ge1$ e $|xy|\le p$, mas com $i=0$ dá $xz=0^{2p-1}\notin L$. Mas outro corte válido da mesma palavra, $y=00$, bombeia dentro da linguagem para todo $i\ge0$. O lema só é contrariado quando todos os cortes válidos falham, e é por isso que a prova de $0^n1^n$ abaixo analisa a forma geral $y=0^k$ em vez de um corte concreto.

Exibir um corte que funciona numa palavra também não prova regularidade. O lema exige que toda a palavra suficientemente comprida de $L$ admita algum corte válido que bombeie dentro de $L$; uma palavra isolada com um corte feliz não chega.

Para $L=\{0^n1^n\mid n\ge0\}$:

1. Supõe que $L$ é regular e seja $p$ o valor dado pelo lema.
2. Escolhe $s=0^p1^p\in L$, com comprimento pelo menos $p$.
3. Considera qualquer decomposição válida $s=xyz$. Como $|xy|\le p$ e $y\ne\varepsilon$, temos $y=0^k$ com $1\le k\le p$.
4. Escolhe $i=0$. Obténs $xz=0^{p-k}1^p\notin L$.

Isto contradiz a exigência de permanecer em $L$ para todo $i$. Não escolhes a posição do corte; o argumento cobre todos os cortes permitidos.

Quando o problema é o comprimento

Para $K=\{a^{n^2}\mid n\ge0\}$, escolhe $s=a^{p^2}$. Em qualquer decomposição, $1\le|y|=k\le p$. Bombeando com $i=2$, o comprimento é $p^2+k$, e

$$p^2<p^2+k\le p^2+p<(p+1)^2.$$

Não há quadrado perfeito entre quadrados consecutivos. Logo, a palavra bombeada sai de $K$.

Usar fecho numa prova negativa

Se $H=\{0^i1^j\mid i\ne j\}$ fosse regular, então $0^*1^*\setminus H$ seria regular por diferença. Mas essa diferença é $\{0^n1^n\mid n\ge0\}$, que acabámos de provar não regular. Logo, $H$ não é regular.

Uma expressão regular, uma construção de autómato ou uma propriedade de fecho podem provar regularidade. O lema da repetição, uma redução por fecho ou palavras distinguidoras podem provar impossibilidade. Escolhe o argumento de acordo com a conclusão que queres.