Aut Matos Finitos Aula 01

SEMANA 2

GRAFOS E AUTÔMATOS:

AUTÔMATOS FINITOS
Profª Drª Mônica Rocha Ferreira de Oliveira [e-mail] Introdução
As linguagens, as de tipo 3 (Hierarquia de Chominsky) são as mais simples, permitindo abordagens de pequena complexidade, grande eficiência e fácil implementação.
Essa abordagem pode ser feita através de 3 diferentes formalismos: operacional ou reconhecedor: Autômato Finito, que pode ser determinístico, não determinístico ou com movimento vazio.
axiomático ou gerador: Gramática Regular
denotacional: Expressão Regular (também pode ser considerado gerador

Sistemas de Estados Finitos
 Um sistema de estados finitos SEF é um modelo matemático de um sistema com entradas e saídas discretas.
 Pode assumir um número finito e pré-definido de estados.
 Cada estado resume somente as informações do passado necessárias para determinar as ações para a próxima entrada.

Sistemas de Estados Finitos
 Podem ser associados a diversos tipos de sistemas naturais e construídos.
 Exemplo: Elevador (1) Não memoriza instruções anteriores. (2) Cada estado sumariza as informações: andar corrente e direção do movimento. (3) As entradas para o sistema são requisições pendentes.
 Outros exemplos de sistemas de estados finitos: analisadores léxicos e processadores de texto Sistemas de Estados Finitos
•

SEF de difícil manipulação:

(1) O cérebro humano, com tamanha complexidade que esta abordagem se torna ineficiente.
(2) O computador onde o estudo adequado da computabilidade exige uma memória sem limite prédefinido.

Autômato Finito
•

Um autômato finito determinístico, ou simplesmente autômato finito, pode ser visto como uma máquina composta basicamente por três partes:

a

a

b

c

c

Controle

b

a

a

Autômato Finito
•

Fita: Dispositivo de entrada que contém a informação a ser processada. A fita é finita à esquerda e à direita. É dividida em células onde cada uma armazena um símbolo. Os símbolos pertencem a um alfabeto de entrada. Não é
possível