Considere a tabela de estados abaixo:
(a) Elimine os estados redundantes para obter uma nova tabela de estados.
(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. - Para x=0:
-
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. - Para x=0:
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.