Considere a tabela de estados abaixo:
(a) Elimine os estados redundantes para obter uma nova tabela de estados.
Estado atual Q^n Estado Seguinte/Saída <br> Q^n+1 / Z
x=0 x=1
A F / 0 E / 0
B G / 0 B / 1
C B / 0 H / 0
D F / 0 H / 0
E G / 0 C / 0
F G / 0 F / 1
G E / 0 A / 0
H G / 0 A / 0

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 Q^n x=0 x=1
A F / 0 E / 0
B G / 0 B / 1
C B / 0 H / 0
D F / 0 H / 0
E G / 0 C / 0
F G / 0 F / 1
G E / 0 A / 0
H G / 0 A / 0
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 Q^n x=0 x=1
A F / 0 E / 0
B G / 0 B / 1
C B / 0 H / 0
E G / 0 C / 0
F G / 0 F / 1
G E / 0 A / 0
H G / 0 A / 0

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