Autómato
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.