Refaça o exercício do Reconhecedor de Sequência 1101 (com Máquina de Mealy, vista em sala de aula) com a seguinte atribuição de códigos aos estados: A=1 1, B=0 1, C=1 0 e D=0 0.

Passo 1

O enunciado pede para redesenhar um reconhecedor de sequência 1101 usando uma Máquina de Mealy, agora com os estados codificados como A=11, B=01, C=10 e D=00 em bits (y₁y₀). Vamos precisar definir quais prefixos da sequência estamos retendo em cada estado e depois derivar a tabela de transição e as funções lógicas para os próximos estados e saída.

Passo 2

Precisamos de 4 estados que representem o maior sufixo da entrada lida que seja também prefixo de “1101”:
— A: nenhum prefixo reconhecido (sufixo “ ”).
— B: já lemos “1”.
— C: já lemos “11”.
— D: já lemos “110”.
Com esses significados, montamos as transições de Mealy (saída associada à aresta):
— Em A: ao ler 1→B / z=0; ao ler 0→A / z=0.
— Em B: ao ler 1→C / z=0; ao ler 0→A / z=0.
— Em C: ao ler 1→C / z=0 (pois “111” ainda tem sufixo “11”); ao ler 0→D / z=0.
— Em D: ao ler 1→B / z=1 (reconheceu 1101); ao ler 0→A / z=0.

Passo 3

Agora atribuímos as codificações y₁y₀ aos estados e construímos a tabela completa da Máquina de Mealy, listando (y₁,y₀), entrada x, próximos (Y₁,Y₀) e saída z:
Apresentamos a tabela:
c c | c | c c | c Estado&y1&y0&x&Y1&Y0&zhline A&1&1&0&1&1&0 A&1&1&1&0&1&0 B&0&1&0&1&1&0 B&0&1&1&1&0&0 C&1&0&0&0&0&0 C&1&0&1&1&0&0 D&0&0&0&1&1&0 D&0&0&1&0&1&1

Passo 4

Para implementar em lógica sequencial, derivamos as funções via mapas de Karnaugh. O resultado simplificado é:
$$Y_1 = \overline{x},(\overline{y_1}+y_0) ;+
; x,(y_1 \oplus y_0)$$
Y1 = x,(y1+y0) ;+ ; x,(y1 oplus y0)
Y0 = y1,y0 ;+ ; y1,y0 ;+ ; y1,y0,x

Resposta

A Máquina de Mealy para reconhecer 1101 com estados codificados A=11, B=01, C=10, D=00 fica definida pela tabela e pelas funções:
Tabela de transição:
c c | c | c c | c y1&y0&x&Y1&Y0&zhline 1&1&0&1&1&0 1&1&1&0&1&0 0&1&0&1&1&0 0&1&1&1&0&0 1&0&0&0&0&0 1&0&1&1&0&0 0&0&0&1&1&0 0&0&1&0&1&1
Equações simplificadas:
Y1 = x,(y1+y0) + x,(y1 oplus y0)
Y0 = y1,y0 + y1,y0 + y1,y0,x
z = y1,y0,x

Exercícios relacionados