pesquisas

5

2 Autômatos Finitos
Os autômatos finitos constituem um modelo útil para muitos elementos importantes de hardware e software. Alguns exemplos:
Software para projetar e verificar comportamento de circuitos digitais
Analisador Léxico de um compilador típico (isto é, componente que divide o texto de entrada em unidades lógicas, como identificadores, palavraschave, etc.)
Software para examinar grandes corpos de texto, como páginas Web
Software para verificar sistemas de todos os tipos que tem um número finito de estados distintos, como protocolos de comunicação ou segurança
Estes elementos têm como características estarem a todo o momento em um determinado “estado” de um conjunto finito deles. Como o conjunto é finito a história toda de execução não pode ser memorizada, assim o sistema deve ser projetado a fim de memorizar apenas o que é relevante. A vantagem de usar um número finito de estados é que é possível implementá-lo de uma forma simples em hardware como um circuito, ou em um software que possa tomar decisões examinando apenas um número limitado de dados ou a própria posição no código.
Exemplo de autômato finito: um interruptor que memoriza se está no estado
“ligado” ou “desligado”, e permite que o usuário pressione um único botão cujo efeito será diferente de acordo com o estado em que o interruptor se encontra, ou seja, se ele estiver desligado e for pressionado ele irá ligar, e vice-versa.

Os estados estão representados por círculos, e a ação (ou “entrada”) está representada pelos arcos. Neste caso temos os estados ligado e desligado, e ambos os arcos representam a ação de pressionar o botão. O estado inicial é indicado pela palavra
“início” e por uma seta que leva a este estado. Frequentemente também precisamos

6 indicar um ou mais estados “finais” ou de “aceitação”, que representam que a entrada é
“válida”, neste caso utilizamos círculos duplos para representar tais estados.
Outro exemplo: um autômato que reconhece a