Resumo
Estrutura das máquinas de estados finitos.
Sistemas e Sinais
Diagrama de estados.
Máquinas de Estados Finitos
Tabela de actualização.
Máquinas não-determinísticas.
Luís Caldas de Oliveira
Simulação e bi-simulação.
[email protected]
Instituto Superior Técnico
Sistemas e Sinais – p.1/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.2/23
Luís Caldas de Oliveira
Máquina de Estados Finitos
Esta Aula
Quais os argumentos da função actualizacão?
Há uma grande classe de sistemas que pode ser
caracterizada pelo conceito de estado;
Qual a dimensão do tuplo que define uma máquina
de estados?
esses sistemas evoluem através de uma sequência
de transições de estados;
Qual o significado de gaguejar ?
esta caracterização denomina-se de modelo de
estado.
O que é um máquina receptiva?
O que distingue um máquina não-determinística?
O que significa dizer que uma máquina de estados
simula uma outra?
Luís Caldas de Oliveira
Sistemas e Sinais – p.3/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.4/23
Exemplo
Reconhecedor de Sequência de 3 Zeros
Reconhecedor de três entradas nulas consecutivas:
0/F
x ∈ S inaisEntrada
y ∈ S inaisS aida
-
- Reconhecedor
2
1
1/F
1/F
em que
0/F
1/F
0/V
x ∈ SinaisEntrada = [š → {0, 1}]
x ∈ SinaisSaida = [š → {V, F}]
x = (0, 1, 0, 0, 0, 0, 1, 1, . . .)
s = (1, 2, 1, 2, 3, 3, 3, 1, . . .)
y = (F, F, F, F, V, V, F, F, . . .)
(
V, se (x(n), x(n − 1), x(n − 2)) = (0, 0, 0)
Reconhecedor(x)(n) =
F, no caso contrário
Sistemas e Sinais – p.5/23
Luís Caldas de Oliveira
3
Sistemas e Sinais – p.6/23
Luís Caldas de Oliveira
Actualização de Estados
Máquina de Estados
Um máquina de estados é um 5-tuplo:
0/F
MaqEstados = (Estados, Entradas, Saı́das, actualizacão, estado0)
2
1
1/F
1/F
Estados é o espaço de estados
0/F
1/F
3
Entradas é o alfabeto de entrada
Saı́das é o alfabeto de saída
0/V
estado0 ∈ Estados é o estado inicial
actualizacão : Estados × Entradas → Estados × Saı́das é a
função de actualização
s(0) = 0
(s(n + 1), y(n)) = actualizacão(s(n), x(n)), n = 0, 1, . . .
Luís Caldas de Oliveira
Sistemas e Sinais – p.7/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.8/23
Diagrama de Transição
Reconhecedor de Sequências de 3 Zeros
Estados
Entradas
Saı́das
estado0
0
entrada1/saída1
1
entrada2/saída2
=
=
=
=
{1, 2, 3}
{0, 1}
{V, F}
1
2
actualizacão : Estados × Entradas → Estados × Saı́das
Cada bola representa um estado;
cada estado tem uma etiqueta;
(s(n + 1), y(n))
actualizacão(0, 0)
actualizacão(0, 1)
...
cada arco representa uma transição de estado;
cada arco é etiquetado pela entrada e pela saída
correspondente (entrada/saída).
Sistemas e Sinais – p.9/23
Luís Caldas de Oliveira
=
=
=
=
actualizacão(s(n), x(n))
(0, F)
(0, F)
...
Sistemas e Sinais – p.10/23
Luís Caldas de Oliveira
Stuttering (Gaguejar)
Exemplo: Parquímetro
Um máquina de estados produz um símbolo de saída
e um estado para cada símbolo de entrada
Modelo de estado para um parquímetro mecânico que
aceita moedas de 20 e 50 cêntimos:
Por vezes é necessário tornar explícito que ausência
de entrada significa que não há saída e que a
máquina se mantém no mesmo estado.
Estados
Entradas
Saı́das
estado0
Iremos considerar que os conjuntos de entrada e de
saída incluem um símbolo nulo (stuttering symbol)
=
=
=
=
{0, 1, . . . , 60}
{20cent, 50cent, tique, nulo}
{expirou, 1, 2, . . . , 60, nulo}
0
nulo ∈ Entradas, e nulo ∈ Saı́das
Iremos exigir que todos os estados tenham uma
transição para si próprio:
actualizacão(s, nulo) = (s, nulo)
Luís Caldas de Oliveira
Sistemas e Sinais – p.11/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.12/23
Exemplo: Parquímetro
Máquina Receptiva
Função de actualização:
actualizacão(s(n), x(n)) =


(0, expirou),
se x(n) = tique∧






∧(s(n) = 0 ∨ s(n) = 1)





(s(n)
−
1,
s(n)
−
1),
se x(n) = tique∧




∧s(n)
>1






(min(s(n) + 10, 60), min(s(n) + 10, 60), se x(n) = 20cent





(min(s(n)
+ 25, 60), min(s(n) + 25, 60), se x(n) = 50cent




(s(n), nulo),
se x(n) = nulo
Sistemas e Sinais – p.13/23
Luís Caldas de Oliveira
Uma máquina de estados receptiva possui em cada
estado um arco de saída para todas as entradas possíveis
nesse estado. Por exemplo para Entradas = {a, b, c}:
0
b/0
1
a/1
a/0
b/0
b/1
c/0
0
c/0
a/1
1
b/1
a/0
b/1
c/0
2
a/1
c/1
c/0
b/1
2
c/1
Sistemas e Sinais – p.14/23
Luís Caldas de Oliveira
Máquina Não-determinística
Parquímetro Não-determinístico
Uma máquina de estados não-determinística pode
conter mais do que um arco de saída de um estado para a
mesma entrada. Por exemplo para Entradas = {0, 1}:
Por vezes um modelo menos detalhado pode ser útil para
contruir uma abstração de uma máquina complicada:
{0}/0
0
0
{0,1}/1
{1}/1
{0}/0
{20cent, 50cent}/verde
1
2
{tique}/verde
{20cent, 50cent}/verde
Sistemas e Sinais – p.15/23
Luís Caldas de Oliveira
{tique}/expirou
{20cent, 50cent}/verde
1
Luís Caldas de Oliveira
{tique}/expirou
{tique}/verde
Sistemas e Sinais – p.16/23
Comportamento
Determinísticas e Não-determinísticas
Uma máquina determinística tem uma função de
actualização determinística:
Define-se comportamento da máquina como sendo o par
(x, y) em que y = F(x).
O conjuntos dos Comportamentos:
actualizacão : Estados × Entradas → Estados × Saı́das
Comportamentos ⊂ SinaisEntrada × SinaisSaı́da
Uma máquina não-determinística tem uma função
de actualização não-determinística:
define-se como:
actualizPossiveis : Estados×Entradas → P(Estados×Saı́das)
Comportamentos = {(x, y) ∈ SinaisEntrada×SinaisSaı́da|y = F(x)}
A função de actualização de uma máquina
determinística é um caso particular da função da
máquina não-determinística:
Numa máquina de estados determinística, o conjunto
Comportamentos é o gráfico da função F.
actualizPossiveis(s(n), x(n)) = {actualizacão(s(n), x(n))}
Sistemas e Sinais – p.17/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.18/23
Luís Caldas de Oliveira
Simulação
Equivalência de Máquinas
Considerando Entradas = {1, nulo} e Saı́das = {0, 1, nulo}
0
{1}/1
0
1
{1}/1
{1}/1
0
1
2
{1}/1
0
{1}/0
2
{1}/0
1
{1}/1
{1}/0
1
4
0
{1}/0
(a)
{1}/1 {1}/0
{1}/1
4
{1}/1
Luís Caldas de Oliveira
0
{1}/1
{1}/1 {1}/0
{1}/1
{1}/1
5
{1}/0
{1}/1
3
(a)
{1}/1
{1}/0
3
1
2
(b)
5
(b)
2
(c)
1
{1}/1
A máquina (c) diz-se simula (b) e (a): a máquina (c) é mais
{1}/1
(c)
geral ou abstracta do que (a) ou (b)
Sistemas e Sinais – p.19/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.20/23
Verificação
Formulação da Simulação
Verificar que (c) simula (b): começar ambas no estado
inicial e para cada entrada ver se (c) consegue produzir
uma saída igual à de (b).
Considerando duas máquinas de estados finitos X e Y,
determinísticas ou não. Y simula X se existir um
subconjunto S ⊂ EstadosX × EstadosY tal que:
(estado0X , estado0y ) ∈ S e
0
se (sX (n), sY (n)) ∈ S , então ∀x(n) ∈ Entradas, e
∀(sX (n + 1), yX (n)) ∈ actualizPossiveis X (sX (n), x(n)), existe
(sY (n + 1), yY (n)) ∈ actualizPossiveisY (sY (n), x(n)), tal que:
1. (sX (n + 1), sY (n + 1)) ∈ S e
2. yX (n) = yY (n)
{1}/1
1
{1}/0
0
{1}/1
{1}/1 {1}/0
2
(b)
1
(c)
{1}/1
Ao conjunto S , se existir, chama-se relação de simulação.
Sistemas e Sinais – p.21/23
Luís Caldas de Oliveira
Bi-simulação
0
{1}/1
1
{1}/1
0
2
{1}/0
{1}/1
{1}/0
3
1
{1}/0
{1}/1
4
{1}/1
{1}/1
(a)
5
(b)
2
A máquina (b) diz-se que bi-simula (a): a máquina (b) é
equivalente à máquina (a).
Luís Caldas de Oliveira
Sistemas e Sinais – p.23/23
Luís Caldas de Oliveira
Sistemas e Sinais – p.22/23