Uma máquina de estados finita (FSM - do inglês Finite State Machine) ou autômato finito é um modelo matemático usado para representar programas de computadores ou circuitos lógicos. O conceito é concebido como uma máquina abstrata que deve estar em um de um número finito de estados. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.

Máquinas de estado finitas podem modelar um grande número de problemas, entre os quais a automação de design eletrônico, projeto de protocolo de comunicação, análise e outras aplicações de engenharia. Na biologia e na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, utilizadas para descrever sistemas neurológicos e em linguística para descrever as gramáticas das linguagens naturais.

Conceitos e vocabulário

Um estado descreve um nó de comportamento do sistema em que está à espera de uma condição para executar uma transição. Normalmente, um estado é introduzido quando o sistema não reage da mesma forma para uma mesma condição. No exemplo de um sistema de rádio de carro, quando se está ouvindo uma estação de rádio, o estímulo "próximo" significa ir para a próxima estação. Mas quando o sistema está no estado de CD, o estímulo "próximo" significa ir para a próxima faixa. O mesmo estímulo desencadeia ações diferentes, dependendo do estado atual. Em algumas representações de máquinas de estado finitas, também é possível associar ações a um estado:

Ação de entrada: o que é realizado ao entrar no estado, Ação de saída: o que é executado ao sair do estado.

A transição é um conjunto de ações a serem executadas quando uma condição for cumprida ou quando um evento é recebido. Máquinas de estado são utilizadas para descrever circuitos sequenciais. Diferentemente de um contador que em geral conta eventos, uma máquina de estado costuma ser usada para controlar o evento.

A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.

Representação thumb|250px|right|Fig. 1 Exemplo de máquina de estados SDL thumb|250px|right|Fig. 2 Exemplo de uma máquina de estados finita simples

Diagrama de estados Máquinas de estados finitas podem ser representadas por meio de um diagrama de estados (ou diagrama de transição de estados). Diversas tabelas de transição de estados são usadas, a mais famosa é a mostrada abaixo. A combinação do estado atual (ex: B) com uma condição (ex: Y) determina o próximo estado (ex: C). Através do uso das tabelas podemos representar uma máquina finita de estados que contenha informações completas sobre as ações.

+ Tabela de transição de estados Estado Atual → Condição ↓ Estado A Estado B Estado C Condição X ... ... ... Condição Y ... Estado C ... Condição Z ... ... ...

Máquinas de estados UML

A UML tem uma notação para descrever máquinas de estado. Máquinas de estado UML superam as limitações das FSMs tradicionais, mantendo os seus principais benefícios. Máquinas de estados UML introduzem os novos conceitos de estados aninhados hierarquicamente e regiões ortogonais, enquanto estende a noção de ações. Máquinas de estado UML têm as características de ambas as máquinas de Mealy e Moore. Elas suportam ações que dependem tanto do estado do sistema quanto da condição, como em máquinas de Mealy, assim como ações de entrada e saída que estão associadas com os estados em vez de transições, como em máquinas de Moore.

Máquinas de estados SDL

A SDL é um padrão da União Internacional de Telecomunicações e é uma das melhores linguagens para descrever máquinas de estado, pois inclui símbolos gráficos para descrever as ações na transição:

enviar um evento receber um evento iniciar um temporizador cancelar um temporizador iniciar uma nova máquina de estado simultânea decisão

SDL incorpora tipos básicos de dados chamado Abstract Data Types, uma linguagem de ação, e uma semântica de execução, a fim de tornar a máquina de estados finita executável. Um exemplo é visto na figura 1.

Outros diagramas de estado

Existem várias outras maneiras de se representar uma FSM, assim como mostrado na figura 2.

Um exemplo é o HDL:

Em HDL (Hardware Description Language) ou LDH(Linguagem de Descrição de Hardware) é possível criar máquinas de estado simples e de descrição intuitiva. É feito o uso de estados nomeados para os quais não há valores binários definidos. Em VHDL existem as palavras-chave como TYPE por exemplo, que define o tipo enumerado em VHDL. O projetista lista em nomes simbólicos (diferentes das palavras-chave) todos os possíveis valores que um sinal, variável ou porta que é declarado como sendo deste tipo pode assumir. O valor binário é determinado pelo compilador, deixando o trabalho do projetista mais simples.

Uso

Além de seu uso na modelagem de sistemas reativos aqui apresentados, máquinas de estados finitas são significativos em diversas áreas, incluindo engenharia elétrica, linguística, ciência da computação, filosofia, biologia, matemática e lógica. Máquinas de estados finitas são uma classe de autômatos estudada na teoria dos autômatos e teoria da computação. Em ciência da computação, máquinas de estados finitas são amplamente utilizados na modelagem do comportamento do aplicativo, design de sistemas digitais de hardware, engenharia de software, compiladores, protocolos de rede, e o estudo da computação e linguagens.

Classificação Existem dois grupos: Aceitadores/Reconhecedores e Transdutores.

Aceitadores e reconhecedores thumb|400px|right|Fig. 3 FSM aceitador: analisando a palavra "nice"

Aceitadores e reconhecedores produzem uma saída binária, dizendo sim ou não para responder se a entrada é aceita pela máquina ou não. Todos os estados do FSM estão a dizer se quer aceitar ou não quer aceitar. No momento em que todas as entradas são processadas, se o estado atual é um estado de aceitação, a entrada é aceita, caso contrário é rejeitada. Como regra a entrada são símbolos (caracteres); ações não são usadas. O exemplo da figura 3 mostra uma máquina de estados finita que aceita a palavra "nice". Neste FSM o único estado de aceitação é o número 7.

A máquina também pode ser descrita como a definição de uma linguagem, que conteria todas as palavras aceitas pela máquina e nenhuma das que são rejeitadas; dizemos então que a linguagem é aceita pela máquina. Por definição, linguagens aceitas por FSMs são as linguagens regulares, isto é, uma linguagem é regular se existe alguma FSM que a aceita.

Estado Inicial

O estado inicial é geralmente mostrado desenhando uma seta "apontando para ele a partir de qualquer lugar" (Sipser (2006) p. 34).

Estados de aceitação (ou Estados Finais) 220px|right|thumb|Fig. 4: Representação de uma FSM. Este exemplo mostra uma FSM que determina se um número binário tem um número par ou ímpar de 0's, onde S1 é um estado de aceitação.

Estados de aceitação são aqueles em que a máquina relata que a seqüência de entrada, como processadas ​​até agora, é membro da linguagem que ela aceita. É geralmente representado por um círculo duplo. Um exemplo de um estado de aceitação aparece na figura 4: um autômato finito determinístico (AFD) que detecta se a seqüência de entrada binária contém um número par de 0's. S1 (que também é o estado inicial) indica o estado no qual um número par de 0's foi dado na entrada. S1 é, portanto, um estado de aceitação. Esta máquina vai terminar em um estado de aceitação se a seqüência binária contém um número par de 0's (incluindo qualquer seqüência binária que não contenham 0's). Exemplos de cadeias aceitas por este AFD são: epsilon (a cadeia vazia), 1, 11, 11 ..., 00, 010, 1010, 10110, etc.

Transdutores Transdutores geram uma saída baseada em uma entrada e/ou um estado utilizando ações. Eles são utilizados para aplicações de controle.

A saída produzida por um contador ou uma máquina de estado pode vir diretamente das saídas do flip-flop, ou alguns circuitos lógicos. As duas variações são chamadas de modelo Mealy de circuitos sequencial e modelo Moore.

No modelo Mealy, os sinais de saída também são controlados por sinais de entrada adicionais, enquanto o modelo Moore não possui nenhum controle externos para os sinais de saída gerados.A saída do modelo Moore é função apenas do estado atual do flip-flop.

As saídas de um circuito de tipo Moore serão completamente síncronas em relação ao clock do circuito, enquanto saídas produzidas por um circuito de tipo Mealy podem mudar assincronamente.

Máquina de Moore A FSM utiliza apenas ações de entrada, i.e. a saída depende somente do estado. A vantagem do modelo de Moore é a simplificação do comportamento. Consideremos por exemplo uma FSM de Moore de uma porta de elevador com 4 estados "Aberta", "Fechada", "Abrindo", "Fechando". A máquina de estados reconhece dois comandos: "comando_abrir" e "comando_fechar" que disparam a alteração de estado. A ação de entrada (E:) no estado "Abrindo" liga o motor que abre a porta, a ação de entrada no estado "Fechando" liga o motor na outra direção, fechando a porta. Os estados "Aberta" e "Fechada" não desempenham nenhuma ação. Eles sinalizam para o mundo externo (e.g. para outras máquinas de estado) a situação: "porta está aberta" ou "porta está fechada".

thumb|350px|right|Fig. 5 FSM transdutor: exemplo do modelo de Mealy

Máquina de Mealy A FSM utiliza apenas input actions, i.e. a saída depende da entrada e do estado. O uso de uma FSM de Mealy normalmente leva a uma redução no número de estados. Por exemplo uma FSM de Mealy implementando o mesmo comportamento visto no exemplo de Moore (o comportamento depende no modelo de execução implementado na FSM e irá funcionar e.g. para uma FSM virtual mas não para uma FSM de eventos dirigidos). Existem duas input actions(I:): “inicie o motor para fechar a porta se o comando_fechar (sensor_closed na figura 5) chegar” e “inicie o motor na direção oposta para abrir a porta se o comando_abrir (sensor_opened na figura 5) chegar”.

Na prática modelos mistos são muito utilizados.

Mais detalhes sobre as diferenças e usos dos modelos de Moore e Mealy, incluindo um exemplo executável, podem ser encontrados na nota técnica externa "Modelo de Moore ou Mealy?"(documento em inglês)

Determinismo

Uma distinção adicional está entre autômato determinístico (AFD) e não-determinístico (AFN). No autômato determinístico, para cada estado há exatamente uma transição para cada entrada possível. No autômato não determinístico, pode haver nenhuma, uma ou mais de uma transição de um determinado estado para uma entrada possível.

A FSM com apenas um estado é chamada de FSM combinatória e utiliza apenas input actions. Este conceito é útil quando um número de FSM devem trabalhar juntas, e onde é conveniente considerar uma parte puramente combinatória como uma forma de FSM para se adequar às ferramentas de projeto.

Semânticas Alternativas