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
  1. identificar estados que representem quantos bits já coincidem com o prefixo “01010”;
  2. definir transições para cada entrada (0 ou 1) levando em conta possíveis sobreposições (KMP-like);
  3. emitir saída 1 exatamente ao completar “01010”.

Passo 2

Definimos cinco estados S_0,S_1,S_2,S_3,S_4, onde S_k significa “já reconhecemos um prefixo de tamanho k de 01010”. O estado inicial é S_0 (nenhum bit reconhecido).

Passo 3

Para cada estado e cada entrada x\in\{0,1\}, 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 S_0:
ao ler \,0: vai para S_1 e saída 0
ao ler \,1: vai para S_0 e saída 0
Estado S_1 (prefixo “0”):
ao ler \,0: permanece em S_1 e saída 0
ao ler \,1: vai para S_2 e saída 0
Estado S_2 (prefixo “01”):
ao ler \,0: vai para S_3 e saída 0
ao ler \,1: vai para S_0 e saída 0
Estado S_3 (prefixo “010”):
ao ler \,0: vai para S_1 e saída 0 (porque “0100” acaba em “0”)
ao ler \,1: vai para S_4 e saída 0
Estado S_4 (prefixo “0101”):
ao ler \,0: vai para S_1 e saída 1 (completa “01010”)
ao ler \,1: vai para S_0 e saída 0

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
S_0 vai a S_1/0 vai a S_0/0
S_1 vai a S_1/0 vai a S_2/0
S_2 vai a S_3/0 vai a S_0/0
S_3 vai a S_1/0 vai a S_4/0
S_4 vai a S_1/1 vai a S_0/0

Exercícios relacionados