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.
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;
c) O campo magnético
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;
a) O valor total da corrente
(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.