Aula2 Infoteo

Informática Teórica
Engenharia da Computação

Autômatos Finitos







É um dos modelos computacionais que estudaremos. Porém com uma quantidade extremamente limitada de memória.
O que um computador pode fazer com uma memória tão pequena?
Na verdade, interagimos com tais computadores o tempo todo, pois eles residem no coração de vários dispositivos eletromecânicos.

Autômatos Finitos






O controlador para uma porta automática é um exemplo de tal dispositivo.
As lavadoras de louça/roupa, termômetros eletrônicos, relógios digitais, calculadoras e máquinas de venda automática....
Os autômatos também são chamados de máquinas de estados finitos.

Autômatos Finitos: exemplo
Controlador para uma porta automática de entrada

Sinal de entrada
Estado

Nenhum

Frente

Atrás

Ambos

Fechado

Fechado

Aberto

Fechado

Fechado

Aberto

Fechado

Aberto

Aberto

Aberto

Esse controlador é um computador com apenas 1 bit de memória, capaz de registrar em quais dos dois estados o controlador está.

Autômatos Finitos



Ao começar a descrever a teoria matemática de autômatos finitos, fazemos isso no nível abstrato, sem referˆência a qualquer aplicação específica.



A seguir vamos ver alguns exemplos usando um diagrama de estados e identificar os conceitos de: estado inicial, estado de aceitação ou final, transição. Autômatos Finitos



Uma máquina M1 que recebe cadeias de bits como entrada e aceita somente aquelas que começam com um ou mais zeros seguidos de um ou mais 1’s apenas. Autômatos Finitos







O autômato recebe os símbolos da cadeia de entrada um por um da esquerda para a direita.
Após ler cada símbolo, M1 move de um estado para outro ao longo da transição que tem aquele símbolo como seu rótulo.
Quando ele lê o último símbolo, M1 produz sua saída.
A saída é aceite se M1 está agora no estado de aceitação e rejeite se ele não está.

Autômatos Finitos



Um AF M2 que recebe cadeias de bits e aceita aquelas que possuem 10 como subcadeia

Autômatos