Digital II Atividade - Máquinas de Estados

Prévia do material em texto

FACULDADES SANTO AGOSTINHO 
 
 
 
 
 
 
 
 
 
Lucas Vinicius Martins Batista 
 
 
 
 
 
 
 
 
 
 
 
 
TRABALHO AVALIATIVO ELETRÔNICA DIGITAL II 
 
 
 
 
 
Prof. Nelson Mendes da Silva Filho 
 
 
 
 
 
Montes Claros 
Junho/2020 
MÁQUINAS DE ESTADOS FINITA 
 
Uma máquina de estados finita (FSM - do inglês Finite State Machine) ou 
autômato finito é um modelo matemático usado para representar programas de 
computadores ou circuitos lógicos. O conceito é concebido como uma máquina abstrata 
que deve estar em um de um número finito de estados. A máquina está em apenas um 
estado por vez, este estado é chamado de estado atual. Um estado armazena informações 
sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do 
sistema, até o momento presente. Uma transição indica uma mudança de estado e é 
descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma 
ação é a descrição de uma atividade que deve ser realizada num determinado momento. 
Máquinas de estado finitas podem modelar um grande número de problemas, 
entre os quais a automação de design eletrônico, projeto de protocolo de comunicação, 
análise e outras aplicações de engenharia. Na biologia e na pesquisa da inteligência 
artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, 
utilizadas para descrever sistemas neurológicos e em linguística para descrever as 
gramáticas das linguagens naturais. 
Imagine que desejamos construir um circuito digital para controlar um semaforo. 
Este é um exemplo simples no entanto serve para ilustrarmos a utilidade de máquinas de 
estados finitos. Construir um circuito combinacional simples para controlar o sistema não 
é possível pois há uma sucessão de eventos que deve ser respeitada. Consequentemente, 
algum tipo de memoria sera necessaria. As regras do funcionamento são simples. No 
entanto as elicitamos a seguir para fins de claridade. 
1. Apenas uma das luzes (verde, amarelo ou vermelho podem estar ligadas por 
vez); 
2. O sistema deve iniciar em vermelho para fins de segurança; 
3. A cada unidade de tempo a luz a ser acendida deve mudar obedecendo a 
seguinte ordem: vermelho −→ verde −→ amarelo −→ vermelho −..... 
 
Circuitos Digitais Sincronos (Sequenciais) - 
 
Um circuito seqüencial síncrono consiste de um circuito combinacional e uma rede 
de memória formada por elementos de armazenamento (usualmente flip-flops); 
 ● A rede de memória define o estado atual da máquina de estados, representado 
pelo conjunto de flip-flops; 
● O circuito seqüencial difere de um circuito combinacional puro na medida em 
que o próximo estado será definido não só a partir das entradas atuais, como também do 
estado atual. 
● Logo, as possibilidades de projeto aumentam enormente com uso de circuitos 
seqüenciais 
● O funcionamento dos circuitos seqüenciais pode ser representado por uma 
máquina de estado. 
● O conjunto dos valores armazenados em cada flipflop define o estado atual dessa 
máquina de estado. 
● Há diversas codificações possíveis para a representação do estado atual com o 
conjunto de flipflops, com por exemplo: 
 Binária ; Código Gray ; One Hot 
 
 A máquina de estados representada pelo circuito seqüencial síncrono pode ser 
implementada de duas maneiras equivalentes entre si: 
 Máquina de Moore; Máquina de Mealy 
 
Conceito de estado 
Um estado descreve um nó de comportamento do sistema em 
espera de uma condição para executar uma transição. Normalmente, um estado é 
introduzido quando o sistema não reage da mesma forma para uma mesma condição. No 
exemplo de um sistema de rádio de carro, quando se está ouvindo uma estação de rádio, o 
estímulo "próximo" significa ir para a próxima estação. Mas quando o sistema está no 
estado de CD, o estímulo "próximo" significa ir para a próxima faixa. O mesmo estímulo 
desencadeia ações diferentes, dependendo do estado atual. Em algumas representações de 
máquinas de estado finitas, também é possível associar ações a um estado: 
• Ação de entrada: o que é realizado ao entrar no estado, 
• Ação de saída: o que é executado ao sair do estado. 
A transição é um conjunto de ações a serem executadas quando 
condição for cumprida ou quando um evento é recebido. Máquinas de estado são utilizadas 
para descrever circuitos sequenciais. Diferentemente de um contador que em geral conta 
eventos, uma máquina de estado costuma ser usada para controlar o evento. 
 
A máquina está em apenas um estado por vez, este estado é chamado de estado 
atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças 
desde a entrada num estado, no início do sistema, até o momento presente. Uma transição 
indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para 
que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada 
num determinado momento. 
 
 
Estrutura Geral 
 
Fonte: SlidePlayer.com.br 
 
 
 
Máquinas de Mealy e de Moore 
 
A Máquina de Moore possui uma função que gera uma palavra de saída (que pode 
ser vazia) para cada estado da máquina. Esta saída só depende do estado atual da máquina. 
 Já a Máquina de Mealy é um Autômato Finito modificado de forma a gerar uma 
palavra de saída para cada transição entre os estados. Neste tipo de máquina de estados 
estas palavras de saída dependem do estado atual e do valor das entradas. 
Uma Máquina de Mealy M é autômato finito determinístico com saídas associadas 
às transições e pode ser representada formalmente pela sêxtupla M = (Σ, Q, δ, q0, F, ∆), 
onde: Σ é um alfabeto de símbolos de entrada. Q é um conjunto de estados possíveis do 
autômato, o qual é finito. δ é a função programa ou de transição δ: QxΣ Æ Qx∆* q0 é o 
estado inicial do autômato, tal que q0 é elemento de Q F é um conjunto de estados finais 
tal que F está contido em Q. ∆ é um alfabeto de símbolos de saída. 
O processamento de uma Máquina de Mealy para uma dada entrada w consiste na 
aplicação sucessiva da função programa para cada símbolo de w (da esquerda para a 
direita), até ocorrer uma condição de parada. Caso a saída da função programa seja uma 
palavra vazia, nenhuma gravação é realizada, ou seja, a cabeça da fita não se move. Porém 
se todas as transições de uma determinada máquina de Mealy gerarem saídas vazias, então 
esta se comporta como um Autômato Finito. 
Já uma Máquina de Moore M, como dito anteriormente, é um Autômato Finito 
Determinístico com suas saídas associadas aos estados. É representada formalmente por 
uma septupla M = (Σ, Q, δ, q0, F, ∆, δS), onde: 3 Σ é um alfabeto de símbolos de entrada. 
Q é um conjunto de estados possíveis do autômato, o qual é finito. δ é a função programa 
ou de transição δ: QxΣ Æ Q q0 é o estado inicial do autômato, tal que q0 é elemento de Q 
F é um conjunto de estados finais tal que F está contido em Q. ∆ é um alfabeto de símbolos 
de saída. δS é a função de saída δS: Q Æ ∆* a qual é uma função total. O processamento de 
uma Máquina de Moore ocorre da mesma forma que na máquina de Mealy, assim como o 
tratamento de saídas vazias. Assim como a Máquina de Mealy, se todos os seus estados 
gerarem saída vazia, ela também se comporta como um Autômato Finito. 
 
Exemplos 
Máquina de Mealy 
 Uma aplicação comum e freqüentemente recomendada para os autômatos com 
saída é o projeto de diálogo entre um programa (de computador) e o seu usuário. Neste 
caso, o diálogo poderia se dar de duas maneiras: ser comandado pelo programa ou pelo 
usuário 
 
Máquina de Moore 
 Um exemplo comum de aplicação do conceito de Máquina de Moore é o 
desenvolvimento de Analisadores Léxicos de compiladores ou tradutores de linguagens em 
geral. Basicamente, um analisador léxico é um Autômato Finito (em geral, determinístico) 
que identifica os componentes básicos da linguagem como, por exemplo, números, 
identificadores, separadores,etc. Uma Máquina de Moore como um Analisador Léxico é 
como segue: • um estado final é associado a cada unidade léxica; • cada estado final possui 
uma saída (definida pela Função de Saída) que descreve ou codifica a unidade léxica 
identificada; • para os demais estados (nãofinais) a saída gerada é a palavra vazia. 
 
 
Fonte: SlidePlayer.com.br 
 
 
Fonte: SlidePlayer.com.br 
 
Conclusão 
 
Um grande utilidade das máquinas de estados são no comportamentos de agentes 
inteligentes em jogos eletrônicos,pois sua simplicidade e eficiência se identificam com os 
requisitos de desempenho de aplicações em tempo real. 
REFERÊNCIAS 
 
 
BRITO,R.C; MARTENDAL,D.M; OLIVEIRA,H.E.M- Máquinas de Estados Finitos de 
Mealy e Moore. Disponivel em: 
http://www.inf.ufsc.br/~j.barreto/trabaluno/TC_roberta_diogo_henrique.pdf . Acessado 
em: 06 de junho de 2020. 
 
 
FACOM – Máquinas de Estados Finitos. Disponivel em: 
http://www.facom.ufu.br/~abdala/sd/MEFs.pdf. Acessado em: 06 de junho de 2020. 
 
 
SILVA,G.P- Circuitos Sequenciais. Disponivl em: 
https://dcc.ufrj.br/~gabriel/circlog/Sequenciais.pdf. Acessado em: 06 de junho de 2020.