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-\

Álvares de Azevedo Coloquial

Em “Noite na Taverna” de Álvares de Azevedo os cinco últimos bebedores que estão de pé – Solfieri, Bertram, Gennaro, Claudius Hermann e Johann – começam a contar as passagens horríveis de suas vidas.

Aos dezoito anos Gennaro era aprendiz de pintor, e vivia na casa de seu mestre. O mestre tinha uma linda filha de quinze anos, chamada Laura, que todas as noites antes de ir dormir dava um beijo na testa do aprendiz. Um bela noite não havia ninguém em casa, exceto por Gennaro e Laura, ele acordou com a mocinha abraçada a ele. O texto que segue é o seguinte:

“O fogo de meus dezoito anos, a primavera virginal de uma beleza, ainda inocente, o seio seminu de uma donzela a bater sobre o meu, isso tudo ao despertar dos sonhos alvos da madrugada, me enlouqueceu…”

Daí comecei a pensar como a situação seria descrita numa linguagem mais coloquial e cheguei no seguinte:

“O cara numa idade em que só pensa em sacanagem, acorda de madrugada com uma gatinha de 15, só de camisola, agarrada nele, e juntando isso com a terrível ereção matinal… Putz, não dava pra não comer!”

Seja como for, todas as manhãs a jovenzinha ia no quarto de Gennaro, mas acaba em tragédia. Pena.

Matadouro 5

Billy Pilgrim ocasionalmente lembra do futuro. Na verdade ele revive o futuro, e o passado também. Ele levanta da cama do motel onde está curtindo sua Lua de Mel e ao passar pela porta do banheiro sua continuidade temporal o leva para um campo de prisioneiros na Segunda Guerra Mundial, um terrível balde de água fria, na minha opinião. Quando volta do banheiro sua esposa diz “senti sua falta”, mas Billy Pilgrim replica “EU senti sua falta”.

O auge da coisa foi quando os Trafalmadorianos o levaram em sua nave espacial para sevir de atração no zoológico de seu planeta natal, onde ficou exposto junto com a atriz pornô Montana Wildhack (é seu safado, eles fazem sexo). No momento da captura Billy Pilgrim pergunta “por que eu?”, e a resposta “Por que você? Por que nós? Porque sim. Já viu um inseto preso no âmbar? É exatamente assim que vemos esse momento, não poderia ser de outra forma.” Os Trafalmadorianos vivem em quatro dimensões, e enxergam o tempo em extensão, como enxergamos distâncias, e como nós podemos ir e voltar por uma estrada, eles podem fazer o mesmo no tempo. E assim também pode Billy Pilgrim, exceto que ele não consegue escolher quando acontece nem pra quando vai, e ele não pode mudar nada, apenas reviver (ou pré-viver).

Essa é uma pequena parte (que lembro, demorei a escrever isso) do livro Matadouro 5, de Kurt Vonnegut, que trata da vida de Billy Pilgrim, suas viagens pelo próprio tempo, especialmente sua participação na Segunda Guerra Mundial, que aliás não teve nada de heróica, parece mais que ele foi tropeçando pela Europa até chegar em Dresden e testemunhar sua destruição pelas bombas incendiárias dos aliados. Este bombardeio causou o dobro de mortes que a bomba de Hiroshima, e acabou com uma linda cidade (antes/depois), além de cozinhar vivos quase todos os habitantes.

O tom do livro é fatalista, como se pode perceber pela fala dos Trafalmadorianos, e mais do que uma crítica à guerra (como eu esperava) é uma reflexão sobre a condição humana. Sobre se podemos mesmo ser de outro jeito ou o que deve mudar é a forma de encarar os acontecimentos.

A forma de narrativa é fragmentada, pequenos pedaços de história, na maioria das vezes sem a conexão cronológica que se esperaria, mas que eu achei extremamente agradável. Acredito que li Matadouro 5 numas seis viagens de ônibus.

E como resenhista amador me dou o direito de ir embora sem mais nem menos. Até logo e leia esse livro. ;)

Automatos Finitos em Python

Seu computador computa, sua calculadora computa, uma flor computa, você computa, enfim, o universo inteiro computa. Uma verdadeira computaria.

Se encararmos qualquer estado (apagado, aceso, em movimento, triste, com fome) como informação, todo processo que altera esse estado, altera também a informação. Ou melhor, processa a informação, atividade comumente atribuída aos computadores, mas que é feita pelo universo desde que… desde de sempre! (Se é só isso que o universo faz, aí é outra história.)

Pra saber se alguma máquina de computação estava computando direito ou ainda qual seria seu poder computacional, um modelo matemático formal que dissesse “isso aqui é uma computação” era necessário. O modelo que usamos hoje é a máquina de turing, e seu criador, Alan Turing, foi recompensado por essa contribuição sendo levado (dizem alguns) à morte. Mas estou dispersando, isso também é outra história.

Não vou falar aqui da máquina de turing (ainda não cheguei nela em Informática Teórica), e sim de Autômatos Finitos Determinísticos (AFDs pra encurtar). Trata-se de uma máquina mais simples com propósito restrito: determinar se uma string de entrada é parte de uma dada linguagem ou não.

Uma explicação mais elaborada sobre linguagens (no contexto computacional) pode ser encontrada na entrada “Linguagem Formal“, na Wikipedia, no entanto darei alguns exemplos. Usando o alfabeto (os símbolos possíveis da linguagem) {0, 1}, podemos ter a linguagem composta das strings que começam com “110” e terminam com qualquer coisa; a linguagem das strings que terminam em “0”; ou a linguagem das strings que possuem a substring “10101”.

Se fossem nomes de arquivos no unix, poderíamos listar os membros das linguagens dos exemplos anteriores com os comandos: ls 110* ; ls *0 ; ls *10101*

Autômatos Finitos Determinísticos

As linguagens reconhecidas por AFDs são chamadas regulares, e se você pensou no que eu penso que pensou, então está certo! As strings que fazem parte dessas linguagens regulares são aquelas reconhecidas pelas expressões regulares. Na verdade toda expressão regular tem um AFD equivalente e vice-versa.

Vamos a coisas mais estruturais. Um AFD é composto de

  • estados: sua memória;
  • alfabeto: caracteres usados para formar as entradas a serem testadas pelo autômato;
  • transições: o coração do autômato, diz para qual estado deve ir baseado no símbolo (ou caractere) lido na entrada, e no estado atual (é aqui que entra a função de memória dos estados);
  • estado inicial: onde deve começar a brincadeira;
  • estados finais: se o processamento terminar num estado de final, a string de entrada é considerada válida.

Em símbolos costuma ser assim (na mesma ordem da lista anterior):

M = (Q, Σ, δ, s, F)

Implementação em Python

Tudo muito legal, mas bom mesmo é quando tem código pra nos poupar do trabalho macacal de ficar rodando o AFD na mão, e melhor ainda se o código for em Python. :D

Essa implementação recebe uma 4-upla representando o autômato, mais a string a ser avaliada, retornando True ou False para indicar se a string faz parte da linguagem descrita pelo AFD, ou retorna None, para indicar parâmetros inválidos.

(
ALPHABET,
TRANSITION_FUNCTION,
START_STATE,
FINAL_STATES
) = range(4)

Como você deve ter reparado, o implementação em python recebe uma 4-upla, em lugar da 5-upla descrita anteriormente. O motivo é porque a lista de estados já está embutida na hash table que descreve a função de transição.

def process_string(machine, string):
    if not validate_machine(machine) or
       not validate_string(machine[ALPHABET], string):
        return None    # Processamento do automato.
    state = machine[START_STATE]
    for char in string:
        state = machine[TRANSITION_FUNCTION][state][char]

return (state in machine[FINAL_STATES])

As funções validate_* apenas testam a validade dos parâmetro, a implementação pode ser vista no código fonte (lá embaixo).

Exemplo

O AFD usado como exemplo reconhece a linguagem, sobre o alfabeto {0, 1}, composta de todas as strings que começam com 0, mais a string vazia. Sua representação em forma de grafo é a seguinte (hmm, parece um sapo de óculos):

AFD

Na formalidade, esse autômato M é descrito assim:

M = (Q, Σ, δ, s, F)

  • Q = {q1, q2}
  • Σ = {0, 1}
  • δ(q1, 0) = q1
    δ(q1, 1) = q2
    δ(q2, 0) = q1
    δ(q2, 1) = q2
  • s = q1
  • F = {q1}

Versão pythonizada do autômato:

  • Q: não é usado pelos motivos descritos acima
  • Σ: alphabet = set(['0', '1'])
  • δ: trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'}, 'q2' : {'0' : 'q1', '1' : 'q2'}}
  • s: start_state = 'q1'
  • F: final_states = set(['q1'])

Chamo atenção para a forma de implementação da função de transição, usando dicionários. Dessa forma o equivalente pythonico à forma δ(q1, 0) é trans_func['q1']['0'].

Agora o código para testar algumas strings nesse AFD:

if __name__ == '__main__':
    alphabet = set(['0', '1'])
    trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'},
                  'q2' : {'0' : 'q1', '1' : 'q2'}}
    start_state = 'q1'
    final_states = set(['q1'])
    machine = (alphabet, trans_func, start_state, final_states)
    strings = ['000011111000101010101000', '000011',
               '1', '10', 'a01', '']

for string in strings:
        result = process_string(machine, string)
        if result != None:
            print '%s = %s' % (string, result)

Código-fonte: automato.py

Agora você pode programar seus autômatos e testá-los mais rapidamente, além de gastar menos papel no processo, porque esse mundo está se acabando!