Um autómato funciona como um reconhecedor de uma determinada linguagem e serve para
modelar uma máquina ou, se quiserem, um computador simples. É usado, por exemplo, em
editores de texto para reconhecer padrões. Um conceito fundamental nos autómatos é o
conceito de estado. Este conceito é, de facto, aplicado a qualquer sistema, por
exemplo, à nossa televisão. As noções de estado e sistema são tão omnipresentes que
foi desenvolvido uma campo de conhecimento chamado ``Teoria dos Sistemas''. Uma televisão
pode estar ligada(on) ou desligada (off). Temos então um sistema com dois
estados que podemos representar pelo seguinte diagrama:
A um nível mais detalhado, podemos desejar diferenciar os canais, caso em que podemos ter
centenas de estados: um para ``desligada'' e os restantes significando ``ligada no canal i''.
De modo semelhante, uma máquina de lavar pratos pode estar num estado ``desligada'' ou
``ligada num determinado programa''. Em qualquer dos exemplos acima, existe um número finito
de estados. Neste capítulo estaremos sempre a ``lidar com máquinas'' com um número
finito de estados. Dada uma televisão, ela não está apenas num dos estados possíveis:
somos capazes de fazer mudar a televisão de estado. Esta opção, tal como na figura
acima, será indicada através de arcos dirigidos e suas etiquetas. A nossa figura
funciona assim como um diagrama de estados e como um diagrama de transições.
Uma sequência de acções carregaBotao faz com que a televisão acabe no estado on,
se começarmos com ela ligada e carregarmos no botão um número par de vezes ou então se
ela no início estiver desligada e houver um número ímpar de carregaBotao. Se o
estado inicial for o off e o estado final desejado for o on,
então todas as sequências finitas de carregaBotao com comprimento ímpar têm
como resultado o pretendido.
Next: Autómatos Finitos Deterministas Up: Autómatos Finitos Previous: Autómatos Finitos