Aula2 Infoteo
1215 palavras
5 páginas
Informática TeóricaEngenharia 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