Material Maquinas de Estado

an

Sistemas de Estados Finitos
AF Determinísticos
(H&U, 1979) e (H;M;U, 2001)
1

Sistemas de Estados Finitos
• Uma máquina de estados finitos é um modelo matemático de um sistema com entradas e saídas discretas.
• O sistema pode estar em qualquer um de um número finito de estados.
• O estado do sistema sumariza a informação relativa às entradas passadas que é necessária para determinar o comportamento do sistema nas próximas entradas.
2

Memória Limitada
• AF são exemplos de modelos de computadores com memória limitada.
• Já vimos um exemplo na primeira aula de um AF modelando um interruptor On/Off
– O interruptor “se lembra” se ele está no estado “on” ou “off” e permite o usuário apertar um botão cujo efeito é diferente, dependendo do seu estado.

• Mas, o que um computador com memória limitada pode fazer????

• Muitas coisas úteis!

3

Exemplos
• Controlador de porta automática que abre no meio
– Tem um sensor na frente e outro atrás da porta (para não bater em quem está atrás). O controlador está em 1 dos 2 estados: aberto, fechado e as transições seriam:
•
•
•
•

Frente (que faz a porta abrir e segurar aberta)
Atrás (que deixa a porta fechada ou mantém aberta)
Ambas (pessoas estão na frente atrás)
Nenhuma (não há pessoas nem na frente nem atrás)

4

Exemplos

• Mecanismo de controle de um elevador
– O mecanismo não se lembra das requisições de serviços anteriores,
• cada estado sumariza somente as informações de andar atual e direção (para cima ou para baixo).

– As entradas para o sistema são as chamadas a serem atendidas.
5

Exemplos

• Na computação, um AF é um modelo útil para projetar vários tipos de sistemas:
– Busca de cadeias em editores de textos. No Word, por exemplo, podemos expressar as cadeias com os caracteres curinga * e outros especiais.

6

Exemplos
• Analisadores léxicos (AL) de compiladores. O AL é a interface entre o programa fonte e o resto do compilador. Ele é responsável por:
• “empacotar” os caracteres do programa e lhes dar um