Gerando Grafos de Automatos Finitos

Acrescentei uma função para gerar grafos no formato DOT dos autômatos finitos determinísticos usados naquele programa do meu último post sobre autômatos. Com isso tenho uma implementação que funciona mais uma visualização decente.

A função de geração é mostrada a seguir. Perdoe usar pontos como identação, é que o wordpress (sem plugins) foi amaldiçoado por um programador corcunda de COBOL com a incapacidade de indentar. O código decente pode ser visto em automato.py

def generate_graph(trans_func, start_state, final_states):
....states = trans_func.keys()
....states.sort()
....dot_graph = 'digraph finite_state_machine {\n'
....dot_graph += ' rankdir=LR;\n'
....dot_graph += ' edge [fontname=arial,fontsize=11]\n'
....dot_graph += ' node [fontname=arial,fontsize=11,shape=doublecircle];'
....dot_graph += ' '.join(final_states)
....dot_graph += ';\n'
....dot_graph += ' node [shape=circle,size=8]\n'
....dot_graph += ' start [shape=point]\n'
....dot_graph += ' start -> %s\n' % start_state
....for state in states:
........values = trans_func[state].keys()
........values.sort()
........for value in values:
............dot_graph += ' %s -> %s [label=%s]\n' % \
....................(state, trans_func[state][value], value)
....dot_graph += '}\n'
....return dot_graph

(Queria ter colocado “Bitstream Vera Sans” no lugar de “Arial” como fonte, mas por motivos além da minha vontade estou num windão.)

O autômato no formato DOT é visto abaixo. Para fazer a seta que indica o estado inicial e que não parte de nenhum dos nós usei shape=point no nó start, cujo nome nem aparece por causa da forma escolhida.

digraph finite_state_machine {
....rankdir=LR;
....edge [fontname=arial,fontsize=11]
....node [fontname=arial,fontsize=11,shape=doublecircle];q1;
....node [shape=circle,size=8]
....start [shape=point]
....start -> q1
....q1 -> q1 [label=0]
....q1 -> q2 [label=1]
....q2 -> q1 [label=0]
....q2 -> q2 [label=1]
}

Tentei gerar um png mas saiu muito feio, cheio de rebarbas, a imagem abaixo foi gerada a partir do SVG gerado pelo dot (com o comando: dot -T svg -o afd.svg afd.dot).

AFD

Nota: para usar o dot é preciso instalar o pacote graphviz num sistema Debian/Ubuntu; se por algum motivo estranho você estiver no Windows pegue o GraphViz aqui.

Ereséva – codinome Azevedo (ex-Colligo)

No último episódio o Colligo havia sido citado positivamente no Ars Technica, mas logo após aconteceu de descobrirmos através de um comentário que o nome Colligo pertencia a uma empresa gold parceira da Microsoft. O humor do universo em que vivemos é mesmo insuperável, me pergunto se existirá algum universo chato onde só aconteceriam coisas sem graça.

Depois de muita procura Kenneth apareceu com o nome Ereséva, que em Tupi quer dizer algo como “o quê você quer dizer”. O problema de trademark estava acabado, mas não o de pronúncia, então durante uma reunião onde todos falaram o nome das formas mais variadas e criativas, Lauro (não o Moura, mas o Lauro sênior, que acha que blog é coisa de miguxo) saiu com Azevedo. Birunko (que é um miguxo que também não tem blog), acrescentou que numa linguagem há muito esquecida Azevedo significava “aquele que faz VoIP”. E assim foi escolhido o codinome totalmente não oficial do projeto.

AzeVoIP
Álvares de Azevedo, o garoto propaganda totalmente não oficial do Ereséva

Desde a última vez que falei do Colligo Ereséva várias coisas (além do nome) mudaram, e apesar de ter uns bugs menores vou deixá-los quietos e me concentrar em fazer o VoIP funcionar, porque tá todo mundo perguntando disso. :)

Agora o screenshot obrigatório pra mostrar o estado do codinome Azevedo:

Ereséva

Pra baixar e instalar (e testar e relatar bugs! :D) siga as instruções aqui, lembrando de trocar colligo por ereseva.

Interlude

Certa vez Siouxsie Sioux e Morrissey fizeram um dueto e o resultado foi uma das melhores coisas que seus ouvidos podiam querer experimentar. E fica mais raro ainda porque isso jamais acontecerá novamente: os dois se odiaram.

A música:

Siouxsie:
“Time, is like a dream,
Now, for a time,
you are mine.
Let’s hold fast,
to the dream,
that tastes and sparkles like wine.”

Morrissey:
“who-who knows if it’s real,
or just something we’re both…”

Dueto:
“… dreaming of.
What seems like an interlude now,”

Siouxsie:
“Could be the beginning of love.”

(…)

Morrisey & Siouxsie, Interlude

Nano-Creme Dental

Esse negócio de escovar os dentes tem de acabar – é uma obrigação chata (muito mais chato deve ser usar dentadura, por isso continuo escovando) e quase sempre me corto. Fio dental consegue ser cinco vezes pior.

A tirania da escova de dentes acabará com a invenção do Nanocreme Dental. Na verdade será um líquido, bem parecido com Cepacol (qual o nome genérico disso?), e cheio de nano-máquinas programadas pra destruir o tártaro e seus parentes. Você (ou seu neto) coloca uma quantidade na boca e as nano-máquinas fazem o serviço de limpeza em instantes. As versões mais caras podem até reconstruir dentes danificados “on the fly”.

Vai ser incrível. Mas no tempo presente estou acabado de sono e ainda tenho de ir ali escovar os dentes.

Tudo Que é Vivo Morre

Caveira, Flor

“…encontrou-se com o único mal irremediável, aquilo que é a marca de nosso estranho destino sobre a terra, aquele fato sem explicação que iguala tudo que é vivo num só rebanho de condenados, porque tudo o que é vivo morre”.
Chicó, no “Auto da Compadecida”, de Ariano Suassuna

Qual é a flor verdadeira? A flor na árvore ou a que está murcha? A do começo ou a do final?

Os Trafalmadorianos diriam que existe uma flor perfeita congelada no âmbar do tempo, e que será sempre perfeita nos limites desse tempo.

Update: sim, eu sei, muito emo… muito emo… mas vai passar. P-\