Exercício de Autômato

Conforme o prometido, inicio a sessão NERD, onde vou compartilhar com os leitores parte do dia-a-dia de um estudante de ciência de computação. Claro que pouca gente vai entender, mas este ainda é um blog sobre assuntos aleatórios; e, para os mais curiosos, basta procurar os conceitos não entendidos no pai dos burros.

Transcrevo um exercício que acredito ter resolvido, mas não tenho certeza, sobre autômatos finitos determinísticos (DFA):

Suponha que p e q são estados distinguíveis de um dado DFA A com n estados. Como função de n, qual é o menor limite superior para o tamanho que a menor string que distingue p de q pode ter?

Se p é um estado final de A e q não é, então a string ε de tamanho 0 distingue ambos.
Se q é um estado final de A e p não é, então a string ε de tamanho 0 distingue ambos.
Restam os casos onde p e q são ambos estados finais ou não finais. Sem perda de generalidade, suponho que p e q não sejam estados finais.
Chamemos de w a menor string que distingue p de q. Provarei que o tamanho de w é menor ou igual a (n-1)(n-2)/2, ou:
|w|<=(n-1)(n-2)/2
Seja k o número de estados não-finais de A, 1 < k < n, pois deve haver pelo menos 1 estado final para que p e q possam ser distiguíveis, e já consideramos p e q como não-finais.
Sem perda de generalidade, suponho que w leva p a um estado final, e leva q a um estado não-final, o que distingue ambos.
Seja P={P0,P1...Pj} a sequência dos estados que formam o caminho que leva p a tal estado final, recebendo w. P0=p e Pj é um estado final, sendo j=w e P tem j+1 elementos, ou |P| =j+1
Analogamente, definimos Q={Q0,Q1...Qj}, com Q0=q, e Qj é um estado não final.
Seja PQ a sequência dos pares {Px,Qx}, para todo 0<=x<=j.
PQ={{P0,Q0},{P1,Q1}...{Pj,Qj}}, |PQ|=j+1
Seja G={G1,G2...Gk} o conjunto de estados não finais de A, com k elementos.
Seja F={F1, F2...F(n-k)} o conjunto de estados finais de A, com n-k elementos.
Seja G' o conjunto de pares de estados não finais, ou o conjunto de todos os subconjuntos de G que tenham exatamente 2 elementos. Sabemos que G' contém exatamente k(k-1)/2 elementos se k>=2, que é a combinação de k elementos, tomados 2 a 2; ou |G'|=0, se k<2.
Analogamente, definimos F' como o conjunto dos pares de estados finais, tendo (n-k)(n-k-1)/2 elementos se n-k>=2; ou |F'|=0 elementos ,se n-k<2
Sabemos que todos os pares {Px,Qx}, para todo x < j, pertencem a exatamente um dos conjuntos F' ou G'. Caso contrário, se houvesse um y < j para qual o par {Py,Qy} não pertencesse nem a F' nem a G', ou seja, só um dos estados Py e Qy é final, encontraríamos um caminho possível P'={P0,P1...Py}, correspondente a uma string z (substring de w) que distinguisse os estados p e q, e teríamos
z=y < j=w, e w não seria a menor string a distuinguir p e q.
Provaremos por aburdo que a sequência PQ não tem pares repetidos:
Supomos que há dois pares, tais que {Px,Qx}={Py,Qy}, com x < y. Logo, há um loop em w que pode ser retirado do caminho e há um caminho possível P'={P0,P1...Px,P(y+1)....Pj}, correspondente a uma string z, que leva p a Pj e q a Qj, tal que |z|=|w|-(y-x) < |w|, e w não seria a menor string a distinguir p e q.
Assim, podemos chamar PQ de um conjunto sem elementos repetidos. Subtraímos o conjunto formado pelo par {{Pj,Qj}} do conjunto PQ, para formarmos o conjunto PQ', com j elementos.
Como cada elemento de PQ' pertence só a um dos conjuntos F' e G', formamos uma partição de PQ', formada pelos conjuntos PQF e PQG onde PQF é a intersecção de PQ' e F'. Analogamente, PQG é a intersecção de PQ' e G'.
O número de elementos de PQ' é a soma do número de elementos dos suconjuntos que o particionam, ou:
|PQ'|=|PQF|+|PQG|
Propriedade da intersecção:
|PQF|<=|F'|
|PQG|<=|G'|
Logo, |PQ'|<=|F'|+|G'|=
(k)(k-1)/2+(n-k)(n-k-1)/2, se 1 < k < n-1
ou (n-1)(n-2)/2, se k=n-1
Sabemos, pela combinatória, que |F'|+|G'| é máximo quando k=n-1.
Finalmente, temos:
|PQ'|= j = w <=(n-1)(n-2)/2 c.q.d.

De fato, pra mim não está provado que este é o menor limite superior, mas deixo isso pra depois.

Críticas são bem-vindas!

Pensamento da hora:
"Cansei, mas foi melhor que ver o BBB!"

Abs do Vaps