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:
e
.
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.
— 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:
Apresentamos a tabela:
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)$$
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:
Equações simplificadas: