Autômatos Finitos

Autômatos Finitos
Werther

werther.desenvolva.info

www.desenvolva.info

Autômatos Finitos

Modelo Computacional
É um modelo matemático em ciência da computação que requer uma série de recursos computacionais para estudar o comportamento de um sistema complexo por simulação em computador
Modelo matemático para estudo de computadores, seu funcionamento e arquitetura Autômato Finito (ou máquina de estados finitos) é o modelo mais simples
São bons modelos para computadores com quantidade extremamente limitada de memória werther.desenvolva.info www.desenvolva.info

Autômatos Finitos

Autômatos Finitos
Modelos matemáticos que trabalham em ações dentro de um conjunto finito de estados que variam
(ou sofrem transições) de acordo com as entradas
Uma máquina está a todo o momento em um determinado estado dentro um conjunto finito deles
Exemplo: um interruptor que memoriza se está no estado
“ligado” ou “desligado”, e permite que o usuário pressione um único botão cujo efeito será diferente de acordo com o estado em que o interruptor se encontra, ou seja, se ele estiver desligado e for pressionado ele irá ligar, e vice-versa.

werther.desenvolva.info

www.desenvolva.info

Autômatos Finitos

Exemplo do Cotidiano
Controlador de porta automática

Tabela de Transição de Estados
Estado\Sinal

Nenhum

Frente

Retaguarda

Ambos

Fechado

Fechado

Aberto

Aberto

Aberto

Aberto

Fechado

Aberto

Aberto

Aberto

werther.desenvolva.info

www.desenvolva.info

Autômatos Finitos

Cadeia de Caracteres
Considere o autômato finito M1

Estados: q1 (inicial), q2 (de aceitação) e q3
A cadeia de caracteres (ou palavra) 1101 é aceita ou rejeitada?
E as palavras 0100, 0101, 10100, 110000, 11000?

werther.desenvolva.info

www.desenvolva.info

Autômatos Finitos

Definição Formal
Um autômato finito é um 5-upla
M = (Q, ∑, δ, q0, F), onde:
Q = conjunto finito estados
∑ = conjunto finito