Desenhe uma máquina de estados capaz de detectar o recebimento da sequéncia de entrada serial 01010.
Passo 1
O enunciado pede uma máquina de estados finita que, lendo bit a bit uma entrada serial, emita um sinal de detecção sempre que reconhecer a sequência “01010”. O conteúdo é projeto de autômato (Mealy), e vamos precisar
- identificar estados que representem quantos bits já coincidem com o prefixo “01010”;
- definir transições para cada entrada (0 ou 1) levando em conta possíveis sobreposições (KMP-like);
- emitir saída 1 exatamente ao completar “01010”.
Passo 2
Definimos cinco estados
, onde
significa “já reconhecemos um prefixo de tamanho
de 01010”. O estado inicial é
(nenhum bit reconhecido).
Passo 3
Para cada estado e cada entrada
, calculamos a nova quantidade de bits coincidentes com o começo de 01010, usando a função de falha do próprio padrão (como no algoritmo KMP).
Passo 4
Construímos as transições e a saída (Mealy):
Estado :
ao ler : vai para
e saída
ao ler : vai para
e saída
Estado
ao ler
ao ler
Estado
(prefixo “0”):
ao ler : permanece em
e saída
ao ler : vai para
e saída
ao ler
ao ler
Estado
(prefixo “01”):
ao ler : vai para
e saída
ao ler : vai para
e saída
ao ler
ao ler
Estado
(prefixo “010”):
ao ler : vai para
e saída
(porque “0100” acaba em “0”)
ao ler : vai para
e saída
ao ler
ao ler
Estado
(prefixo “0101”):
ao ler : vai para
e saída
(completa “01010”)
ao ler : vai para
e saída
ao ler
ao ler
Resposta
Diagrama Mealy (estados e transições):
┌─────────┐ 0/0 ┌─────────┐
│ \(S_0\) │───────────────────▶│ \(S_1\) │
│(init) │ │ │
│ │◀───1/0───────────────│ │
└─────────┘ └─────────┘
│1/0 │0/0
│ │
▼ ▼
┌─────────┐ 1/0 ┌─────────┐
│ \(S_0\) │◀───────────────────│ \(S_2\) │
└─────────┘ └─────────┘
│0/0
│
▼
┌─────────┐
│ \(S_3\) │
└─────────┘
│1/0
│
▼
┌─────────┐
│ \(S_4\) │
└─────────┘
│0/1
│
▼
┌─────────┐
│ \(S_1\) │
└─────────┘
Ou, em tabela de transições (Mealy):
Estado | entrada=0 | entrada=1 |
---|---|---|
|
vai a
|
vai a
|
|
vai a
|
vai a
|
|
vai a
|
vai a
|
|
vai a
|
vai a
|
|
vai a
|
vai a
|