Máquina de estado finito

Origem: Wikipédia, a enciclopédia livre.

Uma máquina de estados finitos ou Autômatos Finitos é uma modelagem de um comportamento, composto por estados, transições e ações. 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.

Existem diversos tipos de ação:

• Ação de entrada (no estado): executa a ação quando entra no estado.

• Ação de saída: executa a ação quando sai do estado.

• Ação da entrada (da input): executa a ação dependendo do estado presente ou das condições da entrada.

• Ação de transição: executa a ação quando ocorre uma determinada transição.

Máquinas de estados finitos 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. Através do uso das tabelas podemos representar uma de máquina finita de estados que contenha informações completas sobre as ações.

As máquinas de estados finitos foram originalmente definidas na Teoria de Autômatos e depois retomadas na Teoria da Computação. Elas são largamente utilizadas na modelagem de comportamento de aplicativos, projeto de hardware de sistemas digitais, engenharia de software, no estudo da computação e das linguagens.

[editar] Classificacão

Existem dois grupos: Aceitadores/Reconhecedores e Transdutores.

[editar] Aceitadores e reconhecedores

Eles aceitam/reconhecem sua entrada e usam estados para sinalizar o resultado para o mundo externo. Como regra a entrada são símbolos. Ações não são utilizadas. O exemplo na figura 2 mostra uma máquina de estados finita que aceita a palavra “nice”:

[editar] 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. Dois tipos são apresentados aqui:

Máquina de Moore

A MEF 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. O exemplo na figura 3 mostra uma MEF de Moore de uma porta de elevador. 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".

Máquina de Mealy

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

Uma distinção adicional está entre autômato determinístico (DFA) e não-determinístico (NDFA, GNFA). 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 ou mais de uma transição de um determinado estado para uma entrada possível.

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

[editar] Lógica da MEF

O próximo estado e a saída de uma MEF são uma função da entrada e do estado atual.

[editar] Modelo matemático

Dependendo do tipo podem haver várias definições. Uma máquina de estados finitos tipo aceitador é um quíntuplo <Σ, S, s₀, δ, F>, onde:

• Σ é o alfabeto de entrada (um conjunto de símbolos finitos não vazio),
• S é um conjunto finito de estados não vazio,
• s₀ é o estado inicial, um elemento de S,
• δ é a função de transição de estados: δ: S x Σ → S,
• F é o conjunto de estados finais, um (possivelmente vazio) subconjunto de S.

Uma máquina de estados finitos tipo transdutor é um sêxtuplo <Σ, Γ, S, s₀, δ, ω>, onde:

• Σ é o alfabeto de entrada (um conjunto de símbolos finitos não vazio),
• Γ é o alfabeto de saíida (um conjunto de símbolos finitos não vazio),
• S é um conjunto finito de estados não vazio,
• s₀ é o estado inicial, um elemento de S,
• δ é a função de transição de estados: δ: S x Σ → S,
• ω é 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.

[editar] Otimização

Otimizar uma MEF consiste em encontrar a máquina com o menor número de estados que desempenhe a mesma função. Este problema pode ser resolvido utilizando um coloring algorithm.

[editar] Implementação

[editar] Aplicações de Hardware

Fig. 6 O diagrama de circuito para um contador TTL de 4bits, um tipo de máquina de estados

Em um circuito digital, uma MEF pode ser construída utilizando um dispositivo lógico programável. Um controlador lógico programável, portas lógicas e flip-flops ou relays. 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 MEF.

[editar] Referências

• 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

[editar] Ligações externas

• Description from the Free On-Line Dictionary of Computing
• NIST Dictionary of Algorithms and Data Structures entry
• Hierarchical State Machines