Os primeiros autómatos surgiram há cerca de 250 anos, com o despertar da Revolução Industrial. Estávamos no século XVIII e conceitos de programação e robôs praticamente não figuravam nas mais criativas obras de ficção científica.

Quem foi o espertinho que se lembrou de designar todas estas coisas pelo mesmo nome?! Para respondermos a esta pergunta, precisamos de falar de um outro (outro!) tipo de autómatos, que não habitam o mundo físico, mas sim o mundo intelectual. Lubrifica as tuas engrenagens mentais e vem descobrir estas criaturas fantásticas connosco! 🤩

O autómato que modela esta situação é simplesmente um grafo etiquetado (recorda o que já aprendeste no artigo sobre GRAFOS) com dois estados – ABERTO e FECHADO – e dois tipos de transições – trancar e destrancar – como a figura abaixo ilustra:

Por exemplo, a seta com etiqueta “destrancar” que vai do estado FECHADO para o estado ABERTO indica que se o carro estiver fechado e clicares no botão “destrancar”, então ele vai ficar aberto.

Eis que surge a questão habitual: como podemos transmitir a informação contida neste diagrama a um computador? É simples, basta considerarmos uma sequência (chamemos-lhe “ferrari”) em que cada elemento é um par do tipo ((estado 1, estado 2), transição):

A título ilustrativo, o par ((ABERTO,FECHADO),trancar) indica que o Ferrari passa do estado aberto para o estado fechado ao pressionar o botão de trancar. É intuitivo, certo? 😊

Por muito simples que possam parecer, os autómatos servem para modelar praticamente todas as coisas que “funcionam sozinhas”! Isto significa que os autómatos secretamente governam o nosso mundo e estão infiltrados em micro-ondas, máquinas de lavar louça, semáforos, elevadores... Aliás, o computador ou smartphone que estás a utilizar neste momento é modelado, de forma abstrata, por um autómato bastante sofisticado denominado por Máquina de Turing.

Podemos mesmo dizer que sem autómatos não haveria Computação! 😱

Ao lermos uma palavra, se acabarmos num estado verde (S1, S2 ou S3), então estamos perante uma palavra válida na língua bcesa; se acabarmos no estado vermelho (N), essa palavra é inválida.

Por exemplo, a palavra AC é inválida pois a leitura de um C imediatamente após um A coloca-nos no estado vermelho; de facto, qualquer palavra começada por AC será inválida: uma vez chegados ao estado vermelho, não há forma de regressarmos a um estado verde! Por outro lado, como mencionamos acima, a palavra ABCAB já é bcesa, uma vez que, ao ser lida, os estados percorridos são S1, S3, S2, S1, S3:

Assim, como a leitura de ABCAB termina no estado S3, que é verde, trata-se de uma palavra escrita de forma correta na língua bcesa 😄

Como podes ver, os autómatos desempenham um papel fulcral quer a nível de hardware, quer a nível de software. Por isso, se quiseres fabricar um robô que te leve o pequeno-almoço à cama ou inventar uma língua secreta para comunicares com os teus amigos, já sabes a quem recorrer! 😉