Mostrar código-fonte de Máquina de estados finita

{{Mais notas|data=junho de 2010}}
Uma '''máquina de estados finita''' ('''FSM''' - do inglês ''Finite State Machine'') ou '''[[autômato|autômato finito]]''' é um [[Modelo (matemática) | modelo matemático]] usado para representar [[programa de computador|programas de computadores]] ou [[Porta lógica|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 (ciência da computação)|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 ==
[[Imagem:SdlStateMachine.png|thumb|250px|right|Fig. 1 Exemplo de máquina de estados SDL]]
[[Imagem:Finite state machine example with comments.svg|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.

{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto"
|+ Tabela de transição de estados
|-
! Estado Atual&nbsp;→ <br /> Condição&nbsp;↓ || 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 (linguagem) | 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|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 [[Binário|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 ===
[[Imagem:Fsm parsing word nice.svg|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) ====
[[Imagem:DFAexample.svg|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 S<sub>1</sub> é 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 [[Codificação binária decimal|binária]] contém um número par de 0's.
S<sub>1</sub> (que também é o estado inicial) indica o estado no qual um número par de 0's foi dado na entrada. S<sub>1</sub> é, 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".

[[Imagem:Fsm mealy model door control.svg|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 [http://www.stateworks.com/active/content/en/technology/technical_notes.php#tn10 "Modelo de Moore ou Mealy?"](documento em inglês)

=== Determinismo ===

Uma distinção adicional está entre autômato '''determinístico''' ([[Autômatos finitos determinísticos|AFD]]) e '''não-determinístico''' ([[Autômatos finitos não determinísticos|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 ==

Há outros conjuntos de semântica disponível para representar máquinas de estado. Por exemplo, existem ferramentas para modelagem e lógica para projetar controladores incorporados.<ref>[http://www.csl.sri.com/users/tiwari/papers/stateflow.pdf Tiwari, A. (2002). Formal Semantics and Analysis Methods for Simulink Stateflow Models.]</ref> Eles combinam máquinas de estado hierárquico, gráficos de fluxo e tabelas de verdade para uma linguagem, resultando em um diferente formalismo e conjunto de semântica.<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.8817&rep=rep1&type=pdf Hamon, G. (2005). A Denotational Semantics for Stateflow. International Conference on Embedded Software (pp. 164–172). Jersey City, NJ: ACM.]</ref> A Figura 6 ilustra esta mistura de máquinas de estado e gráficos de fluxo com um conjunto de estados para representar o estado de um cronômetro e um gráfico de fluxo para controlar os tiques do relógio. Estes gráficos, como máquinas de estado originais de Harel,<ref>[http://www.fceia.unr.edu.ar/asist/harel01.pdf Harel, D. (1987). A Visual Formalism for Complex Systems. Science of Computer Programming , 231–274.]</ref> apoiam os estados hierarquicamente aninhados, regiões ortogonais, ações do estado, e as ações de transição.<ref>{{Citar web |url=http://drona.csa.iisc.ernet.in/~kanade/publications/symbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf# |titulo=Alur, R., Kanade, A., Ramesh, S., & Shashidhar, K. C. (2008). Symbolic analysis for improving simulation coverage of Simulink/Stateflow models. Internation Conference on Embedded Software (pp. 89–98). Atlanta, GA: ACM. |acessodata=9 de dezembro de 2011 |arquivourl=https://web.archive.org/web/20110715110405/http://drona.csa.iisc.ernet.in/~kanade/publications/symbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf# |arquivodata=15 de julho de 2011 |urlmorta=yes }}</ref>

== Lógica da FSM ==
[[Imagem:Finite State Machine Logic.svg|thumb|200px|right|Fig. 6 Lógica da FSM (Mealy)]]

O próximo estado e a saída de uma FSM são uma função da entrada e do atual estado. A lógica da FSM é mostrada na figura 6.

== Modelo matemático ==
Dependendo do tipo pode haver várias definições.

Uma máquina de estados finita tipo '''aceitador''' é uma [[enupla|quíntupla]] <''Σ'', ''S'', ''s<sub>0</sub>'', ''δ'', ''F''>, onde:
* ''Σ'' é o alfabeto de entrada (um conjunto finito, não vazio, de símbolos);
* ''S'' é um conjunto finito, não vazio, de estados;
* ''s<sub>0</sub>'' é o estado inicial, um elemento de ''S'';
* ''δ'' é a função de transição de estados: ''δ'': ''S'' x ''Σ'' → ''S'' (em um AFN, seria ''δ'': ''S'' x ''Σ'' → ''P''(''S''), isto é, ''δ''iria retornar um conjunto de estados);
* ''F'' é o conjunto de estados finais, um (possivelmente vazio) subconjunto de S.

Para ambos os FSMs determinísticas e não-determinística, é convencional para permitir ''δ'' ser uma função parcial, ou seja, ''δ''(q, x) não tem que ser definida para cada combinação de q <math> \isin </math> ''S'' e x <math> \isin </math> ''Σ''. Se uma FSM M está em um estado q, o símbolo seguinte é x e ''δ''(q, x) não está definida, então M pode anunciar um erro (ou seja, rejeitar a entrada). Isso é útil em definições de máquinas de estado em geral, mas menos útil ao transformar a máquina. Alguns algoritmos em sua forma padrão podem exigir funções totais.

Uma máquina de estados finita é uma máquina de Turing restrita em que a cabeça só pode "ler" as operações, e sempre se move da esquerda para a direita.<ref>{{citar periódico|último =Black|primeiro =Paul E|data=12 de maio de 2008|título=Finite State Machine|periódico=Dictionary of Algorithms and Data Structures|publicado=U.S. [[National Institute of Standards and Technology]]|url=http://www.nist.gov/dads/HTML/finiteStateMachine.html}}</ref>

Uma máquina de estados finita tipo '''transdutor''' é uma [[enupla|sêxtupla]] <''Σ'', ''Γ'', ''S'', ''s<sub>0</sub>'', ''δ'', ''ω''>, onde:
* ''Σ'' é o alfabeto de entrada (um conjunto finito, não vazio, de símbolos);
* ''Γ'' é o alfabeto de saída (um conjunto finito, não vazio, de símbolos);
* ''S'' é um conjunto finito, não vazio, de estados;
* ''s<sub>0</sub>'' é o estado inicial, um elemento de ''S'';
* ''δ'' é a função de transição de estados: ''δ'': ''S'' x ''Σ'' → ''S'' (em um AFN, seria ''δ'': ''S'' x ''Σ'' → ''P''(''S''), isto é, ''δ''iria retornar um conjunto de estados);
* ''ω'' é a função de saída.

Se a função de saída é uma função do estado e do alfabeto de entrada (''ω'': ''S'' x ''Σ'' → ''Γ'' )essa definição corresponde ao '''modelo de Mealy'''. Se a função de saída depende somente do estado (''ω'': ''S'' → ''Γ'' ) essa definição corresponde ao '''modelo de Moore'''.

Se desconsiderarmos o símbolo primeira saída de uma máquina de Moore, ''ω(s<sub>0</sub>)'', então ela pode ser facilmente convertida em uma máquina de Mealy de saída equivalente definindo a função de saída de cada transição da de Mealy (isto é, rotulando cada extremidade) com o símbolo de saída dado ao estado de destino da de Moore. A transformação inversa é menos simples, porque um estado da máquina de Mealy pode ter rótulos de saída diferentes em suas transições de entrada (extremidades). Cada estado tem de ser dividido em vários estados da máquina de Moore, uma para cada símbolo de saída incidente.<ref name="AndersonHead2006">{{citar livro|autor1 =James Andrew Anderson|autor2 =Thomas J. Head|título=Automata theory with modern applications|url=http://books.google.com/books?id=ikS8BLdLDxIC&pg=PA105|ano=2006|publicado=Cambridge University Press|isbn=9780521848879|páginas=105–108}}</ref>

{{Teoria da computação}}

== Implementação ==
=== Aplicações de Hardware ===
[[Ficheiro:4 bit counter.svg|right|thumbnail|250px|Fig. 7 O [[diagrama de circuito]] para um contador TTL de 4bits, um tipo de máquina de estados]]Em um [[circuito digital]], uma FSM pode ser construída utilizando um [[dispositivo lógico programável]]. Um [[controlador lógico programável]], [[porta lógica|portas lógicas]] e [[flip-flop]]s ou [[relay]]s. Mais especificamente, a implementação de hardware requer um [[registrador]] para armazenar o estado das variáveis, um bloco de lógica combinacional que determina o estado de transição e um segundo bloco de lógica combinacional que determina a saída da FSM. O mais famoso é o [[controlador de Richards]].{{Pesquisa inédita em linha}}

Máquinas de Mealy e de Moore produzem lógica com saída assíncrona, porque há um atraso de propagação entre o flip-flop e saída. Isso causa frequências mais lentas operando na FSM. Uma máquina de Mealy ou de de Moore pode ser convertida para uma FSM tal qual a saída é diretamente de um flip-flop, o que faz a FSM funcionar em frequências mais altas. Este tipo de FSM é chamado às vezes FSM de Medvedev.<ref>{{citar web|url=http://www.vhdl-online.de/tutorial/deutsch/ct_226.htm|título=FSM: Medvedev|acessodata=9 de dezembro de 2011|arquivourl=https://web.archive.org/web/20110719112351/http://www.vhdl-online.de/tutorial/deutsch/ct_226.htm#|arquivodata=19 de julho de 2011|urlmorta=yes}}</ref> Um contador é a forma mais simples desse tipo de FSM.

=== Aplicações de Software ===

Os seguintes conceitos são comumente usados para construir aplicações de software com máquinas de estados finitas:
*[[Programação orientada a autômatos|Programação baseada em autômatos]]
* FSM orientada a eventos
* FSM Virtual (VFSM)

== Referências ==
{{reflist}}
==Bibliografia==
{{Refbegin}}
* Timothy Kam, ''Synthesis of Finite State Machines: Functional Optimization''. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
* Tiziano Villa, ''Synthesis of Finite State Machines: Logic Optimization''. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
* Carroll, J., Long, D. , ''Theory of Finite Automata with an Introduction to Formal Languages''. Prentice Hall. Englewood Cliffs, 1989.
* Hopcroft, J.E., Ullman, J.D., ''Introduction to Automata Theory, Languages and Computation''. Addison -Wesley, 1979.
* Kohavi, Z., ''Switching and Finite Automata Theory''. McGraw-Hill, 1978.
* Gill, A., ''Introduction to the Theory of Finite-state Machines''. McGraw-Hill, 1962.
* Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4
* Tocci, Ronald J., "Sistemas digitais:Princípios e aplicações.", 10ª edição, 2007
{{Refend}}
== Ligações externas ==
* [http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=finite+state+machine Description from the Free On-Line Dictionary of Computing]{{Ligação inativa|1=data=novembro de 2018 }}
* NIST Dictionary of Algorithms and Data Structures [http://www.nist.gov/dads/HTML/finiteStateMachine.html entry]
* [http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm Hierarchical State Machines]

[[Categoria:Teoria da computação]]
[[Categoria:Métodos formais]]
[[Categoria:Eletrônica digital]]