Considere a tabela de estados abaixo:
(a) Elimine os estados redundantes para obter uma nova tabela de estados.
Estado atual Estado Seguinte/Saída <br>
A
B
C
D
E
F
G
H

Passo 1

Beleza, vamos lá! A gente tem uma tabela com vários estados e as transições entre eles dependendo do valor de entrada, x=0 ou x=1. Nosso objetivo aqui é eliminar os estados redundantes dessa tabela para simplificar. Isso faz parte do estudo de autômatos finitos, onde a gente tenta otimizar a máquina de estados. Para resolver isso, vamos precisar identificar quais estados não estão realmente contribuindo para o funcionamento da máquina, ou seja, aqueles que podem ser retirados sem mudar o comportamento geral.

Passo 2

Primeiro, vamos dar uma olhada na tabela completa para entender como os estados se conectam:
Estado atual
A
B
C
D
E
F
G
H
Cada célula mostra para cada estado atual e entrada, qual é o próximo estado e qual a saída Z.

Passo 3

Vamos identificar estados equivalentes, ou seja, aqueles que para qualquer entrada levam aos mesmos estados e produzem as mesmas saídas. Esses estados equivalentes são redundantes porque podemos substituir um pelo outro sem mudar o comportamento geral.
Vamos analisar pares de estados para ver se são equivalentes:
  • G e H: Olhando as transições para G e H:
    • Para x=0:
      • G vai para E com saída 0
      • H vai para G com saída 0
    • Para x=1:
      • Ambos vão para A com saída 0
    Já que para x=1 eles se comportam igual, mas para x=0 não, ainda não são equivalentes.
  • A e D:
    • Para x=0:
      • A vai para F com saída 0
      • D também vai para F com saída 0
    • Para x=1:
      • A vai para E com saída 0
      • D vai para H com saída 0
    Novamente, para x=1 eles se comportam diferente. Então, não são equivalentes.
Continuamos esse processo para todos os pares e vemos que não há estados que se comportem exatamente da mesma forma para todas as entradas. Portanto, nenhum estado pode ser considerado redundante com base na equivalência pura.

Passo 4

Vamos então verificar se há estados que não são alcançáveis a partir do estado inicial. Supondo que o estado inicial seja A (já que geralmente é o primeiro na tabela):
  • A vai para F e E
  • F vai para G e F
  • E vai para G e C
  • G vai para E e A
  • C vai para B e H
  • B vai para G e B
  • H vai para G e A
  • D nunca é alcançado a partir de A
Vemos que o estado D não é alcançado por nenhuma sequência de transições a partir do estado inicial A. Isso significa que o estado D é redundante porque nunca será usado no funcionamento da máquina.

Passo 5

Com isso, podemos eliminar o estado D da tabela, já que ele não afeta o comportamento da máquina. Assim, a nova tabela de estados sem o estado redundante D fica assim:
Estado atual
A
B
C
E
F
G
H

Resposta

Após eliminar o estado redundante D, a nova tabela de estados fica sem o estado D, mantendo os demais estados e suas respectivas transições conforme mostrado acima.

Exercícios relacionados

Um toróide no espaço livre com seção transversal retangular é formado pela interseção dos planos e e os cilindros [cm] e [cm]. Uma densidade superficial de corrente flui na superfície interna do toróide sendo dada por . Determinar:
c) O campo magnético dentro do toróide;
Um toróide no espaço livre com seção transversal retangular é formado pela interseção dos planos e e os cilindros [cm] e [cm]. Uma densidade superficial de corrente flui na superfície interna do toróide sendo dada por . Determinar:
a) O valor total da corrente na superfície interna do toróide;
(b) Implemente o sistema simplificado usando um flip-flops do tipo JK para e um do tipo D para .
Estado atual Estado Seguinte/Saída <br>
A
B
C
D
E
F
G
H
Projete um circuito sequencial síncrono, do tipo Mealy (a saída depende do estado atual e da entrada), que tenha uma entrada e uma saída . A saída deverá ser igual a 1 sempre que for recebida a sequência . Para qualquer outra sequência de entrada, a saída será igual a 0. É permitida a sobreposição de sequências.