Visita a um autômato finito

Autor: Pedro Luis Kantek Garcia Navarro


Venha conosco passear. O ônibus de Turing vai nos levar a 30 excursões pela ciência da computação. Nós veremos monumentos de teoria, avenidas de aplicações, praças algorítmicas e pontos computacionais de interesse, ao longo da estrada. Nosso tour não será uma visita exaustiva (seriam necessárias milhares de excursões), mas abrangerá um bom número de exemplos, técnicas, algoritmos, passado, presente e futuro da nossa ciência.

O nome do ônibus é uma homenagem a Alan Turing, herói da II grande guerra, inglês, matemático brilhante, e alguém que disse, antes de qualquer um pensar em computadores, mais ou menos o seguinte: “se algum dia tivermos computadores, eles deverão funcionar assim e assado”.

Nossos passeios buscarão ser rigorosos, como convém a informáticos. Mas serão leves a ponto de poderem ser entendidos por qualquer pessoa, sem maior esforço do que pensar um pouquinho. Os textos serão adaptações de diversas obras, mas principalmente do livro “The Turing Omnibus”, de ª K. Dewdney, que é autor da idéia do ônibus.

Dito isto, por favor, tomem seus lugares, apertem seus cintos de segurança (nosso ônibus arrisca a balançar um pouquinho) e vamos para a ...

EXCURSÃO Nº1 – VISITA A UM AUTÔMATO FINITO

É comum encontrarmos em nosso dia-a-dia, um engenho eletrônico cuja exata função seja desconhecida ou incerta. Uma maneira de descobrirmos seu funcionamento é desmontar todo o equipamento, pedaço por pedaço, e tentar descobrir sua função, analisando seus componentes de maneira como estes se interligam.

Essa abordagem nem sempre é possível nem é necessária, segundo nossa teoria. Desde que a máquina misteriosa possa mostrar as entradas que aceita e as correspondentes saídas que gera, é possível descobrir o que ela faz. Vamos chamar nossa máquina de “caixa preta”.

Imaginemos uma caixa presta particular (fig 1) , na qual existe um terminal elétrico chamado “entrada”, uma pequena lâmpada chamada “saída”, e um botão chamado RESET. Aparentemente, a máquina aceita dois tipos de voltagens (5 ou 2.5) e vamos representar tais voltagens pelos símbolos 0 e 1.


Dito isto, vamos fazer algumas experiências com a caixa preta. Os primeiro símbolos fornecidos não fazem nenhum efeito sobre a máquina. Entretanto, repentinamente... a lâmpada acende. Nossa seqüência foi aceita. Como experimentadores cuidadosos, nós lembramos qual seqüência acionamos, mas repetindo-a, não conseguimos religar a lâmpada. Estamos quase desistindo, achando que o circuito interno trabalha randomicamente, quando lembramos do botão RESET , e emitimos a mesma seqüência após tê-lo pressionado.

A lâmpada agora acende. Continuando esta experiência, descobrimos outras seqüência que acendem a lâmpada, sempre depois de ter pressionado RESET. Podemos imaginar que o engenho possui algum tipo de equilíbrio interno entre um sinal de entrada e o próximo. Vamos também assumir que existe apenas um número finito de tais estados de equilíbrio. Estas presunções são perfeitamente aceitáveis, se a máquina for manufaturada.

Quando descrita desta maneira, uma caixa preta é um autômato finito. Em termos abstratos, um dispositivo é composto por:

a – Uma coleção finita Q de estados;
b – Um alfabeto finito S de sinais de entrada; e
c – Uma função DELTA que a partir de todas as combinações possíveis (estado atual) e (entrada) determina univocamente o novo estado.

Dois desses estados são específicos: o chamado estado inicial e o estado final. Após pressionar o botão RESET, a máquina entra em estado inicial. Certas seqüências de zeros e uns, levam a máquina ao estado final, que é quando a lâmpada se acende.

Diz-se que um autômato finito aceita uma seqüência de símbolos, quando estes o conduzem ao estado final. Ao conjunto de todas estas seqüências, podemos chamar de linguagem do autômato.

Usando esta terminologia, podemos perguntar: é possível determinar a linguagem do autômato inserido dentro de uma caixa preta? Em outras palavras, nós podemos descrever todas as seqüências binárias que causam o acendimento da lâmpada?

Como o autômato tem apenas um número finito de estado, podemos julgar que a tarefa de descobrir sua linguagem seja razoável. Imaginemos que as seguintes seqüências são aceitas:

0101
0100101
0100100101
0100100100101

Não é preciso ir muito longe para perceber que o autômato está aceitando as seqüências 01(001)01, onde (001) significa “qualquer número de repetições das seqüências 001”. Nós agora podemos construir um diagrama de estado-transição (fig. 2), no qual estados são representados por círculos e transições entre ele, por flechas.


As transições representam a função DELTA. Por exemplo, se o autômato agora está no estado 3, DELTA determina o próximo estado seja 4, se entrar um 1 e 5, se entrar um zero.

Como saber que este diagrama está correto? Infelizmente, isto não é possível. Para ter esta certeza, precisaríamos de uma informação externa nos dizendo que este autômato aceita 6 estados.

Com esta nova informação, é perfeitamente possível estabelecer a linguagem aceita pelo autômato. Uma teoria – aguarde o passeio ao tema “linguagens regulares” - permite estabelecer que o autômato aceita as seis palavras, chamada de 01(001) n01, para n= 0,1,2,3,4,5, então ele aceita todas as palavras no conjunto 01(001) *01.

Autômatos finitos são o tipo mais simples de modelo computacional largamente estudados. Não sei se foi possível perceber, mas estivermos estudando o funcionamento de uma CPU (simples). O saber humano sempre cresce quando consegue estudar um mesmo fenômeno de diversos pontos de vista diferentes e complementares. Por exemplo, para um matemático, o comportamento de colisão de nêutrons tem um aspecto. Um físico verá a mesma ocorrência de uma maneira diferente, e um engenheiro de uma terceira visão. Todas corretas e a explicação do que aconteceu precisa das 3 abordagens.

Nesse sentido, a teoria dos autômatos finitos ajuda a estabelecer as regras de funcionamento de um engenho computacional, abstraindo-se os seus aspectos físicos e elétricos). É matemática pura. Como a matemática, por ser uma criação inteiramente intelectual, não está presa às amarras da realidade nem tem pressa, este estudo resulta fascinante e muito útil.

Na verdade, o estudo de autômatos finitos é uma parte de uma área de estudo bastante mais completa que tem sido chamada de teoria computacional, que é o que os informáticos têm de mais próximo de uma lei fundamental (que tanto falta nos faz).

No próximo mês: viaje conosco por dentro de uma unidade CAT – tomografia computadorizada axial. Veja os princípios, as técnicas e os algoritmos usados.