Autômatos Finitos Deterministicos

Prévia do material em texto

Prof. Willian Magalhães
wmagalhaes@unipar.br
Autômatos 
Autômatos Finitos Determinísticos
UNIPAR – Universidade Paranaense
Curso de Sistemas de Informação
Tópicos anteriores
 Alfabeto
 Símbolos
 Cadeias
 Comprimento de cadeias
 Potenciais de um alfabeto
 Fechamento
 Prefixo, Sufixo, Subcadeia
 Concatenação de cadeias
 Concatenação sucessiva de cadeias
Prof. Willian Magalhães 2
Tópicos anteriores
 Linguagem
 Operações sobre linguagens
• União
• Intersecção
• Diferença
• Concatenação
 Linguagens formais
 Tipos de formalismos
 Hierarquia de Chomsky
Prof. Willian Magalhães 3
Tipos de formalismos
 Reconhecedores
• Recebe uma palavra e retorna um valor para dizer se ela
é ou não da linguagem
 Geradores
• Define um conjunto de regras que podem ser
combinadas para gerar cadeias
 Denotacionais
• Uma expressão que denota de modo geral as palavras
da linguagem
Prof. Willian Magalhães 4
Hierarquia de Chomsky
Prof. Willian Magalhães 5
Linguagens
Livres de Contexto
Linguagens
Sensíveis ao Contexto
Linguagens 
Enumeráveis Recursivamente
Linguagens Regulares
Tipo 0
Tipo 1
Tipo 2
Tipo 3
MT
NORMA
POST
AP
GLC
AFD
AFND
AFS
GR
ER
Autômato Finito Determinístico
 Formalismo reconhecedor
• Recebe uma palavra de entrada
• Com base em um alfabeto, indicar se é aceita ou não
• Exemplo
• Σ = 0, 1
• Aceita todas as cadeias 
• Restrição de cadeias (somente cadeias que terminem 
em 1)
 Baseado no conceito de “máquinas de estados fintas”
Prof. Willian Magalhães 6
Máquina de Estados Finitos
 Conjunto finito de estados
• Um estado representa a “situação atual”
 Mudanças de estados
• Depende do estado atual
• Depende de uma certa entrada (símbolo)
 Não armazena histórico de estados
• Aguarda uma nova entrada, para saber que ação tomar, 
sem depender de estados anteriores
Prof. Willian Magalhães 7
Máquina de Estados Finitos
 Reconhecedor de palavras ou cadeias de caracteres
 Bons modelos para computadores com capacidade de 
memória reduzida (simplicidade)
 Fazem parte de vários dispositivos eletromecânicos do dia-
a-dia
Prof. Willian Magalhães 8
Exemplo (porta automática)
 Porta automática de um shopping
Prof. Willian Magalhães 9
Tapete Fora
Tapete Dentro
Porta
Exemplo (porta automática)
 O controlador da porta pode estar em dois estados:
• aberto
• fechado
 O controlador passa de um estado para o outro
dependendo do estimulo (transição)
Prof. Willian Magalhães 10
São estados finitos, sempre será um ou outro
Exemplo (porta automática)
 Existem 4 condições de entrada possíveis:
• Dentro: indica que uma pessoa esta sobre o tapete de
dentro querendo sair
• Fora: indica que uma pessoa esta sobre o tapete de fora
querendo entrar
• Ambos: indica que existem pessoas nos tapetes de
dentro e de fora
• Nenhum: indica que não tem nenhuma pessoa próximo
à porta
Prof. Willian Magalhães 11
Exemplo (porta automática)
 Representação
Prof. Willian Magalhães 12
Exemplo (porta automática)
 Tabela de transições
Prof. Willian Magalhães 13
Nenhum Dentro Fora Ambos
Fechado Fechado Aberto Aberto Aberto
Aberto Fechado Aberto Aberto Aberto
Estados
Entradas
Transições
Exemplo (interruptor)
Prof. Willian Magalhães 14
 Estados possíveis:
• desligado
• ligado
Exemplo (palavra UNIPAR)
Prof. Willian Magalhães 15
Autômatos Finitos
 Podemos considerar AF como uma máquina,
reconhecedora de cadeias, onde sempre temos uma
resposta afirmativa ou negativa
 Que podem classificadas em 2 tipos:
• Autômatos Finitos Determinísticos (AFD)
• Autômatos Finitos Não Determinísticos (AFND)
Prof. Willian Magalhães 16
AFD – Definição Formal
 Um AFD é uma quíntupla< Σ, 𝑆, 𝑆0, 𝛿, 𝐹 >, onde:
• Σ é o alfabeto de entrada
• 𝑆 é o conjunto finito não vazio de estados
• 𝑆0 é o estado inicial, 𝑆0 ∈ 𝑆
• 𝛿 é a função de transição de estados, 𝛿: 𝑆 𝑥 Σ → 𝑆
• 𝐹 é o conjunto de estados finais, 𝐹 ⊆ 𝑆
Prof. Willian Magalhães 17
Estado INICIAL apenas um estado
Estado FINAL vários estados
AFD – Definições Básicas
 Finito
• O número de estados que envolvidos no sistema é finito
 Determinístico
• Existe somente uma sequencia de estados no AFD para
processar a cadeia
Prof. Willian Magalhães 18
AFD – Representação Gráfica
Prof. Willian Magalhães 19
Estado
Estado inicial
Estado final
Transição 𝛿 𝑆3, I = 𝑆4
AFD – Exemplo
Prof. Willian Magalhães 20
 Identificando os elementos gráficos
 Identificando a quintupla< Σ, 𝑆, 𝑆0, 𝛿, 𝐹 >
AFD – Exemplo
Prof. Willian Magalhães 21
 O autômato recebe símbolos de entrada um a um
 Depois de ler o último símbolo temos uma saída:
• Cadeia aceita ou Cadeia não aceita
AFD – Teste
Prof. Willian Magalhães 22
 𝑎 = 1
 𝑏 = 01
 𝑐 = 11
 𝑑 = 1010
 𝑒 = 0101
 𝑓 = 100001
AFD – Exemplo
Prof. Willian Magalhães 23
 W =< Σ, 𝑆, 𝑆0, 𝛿, 𝐹 >, onde:
• Σ = a, b
• 𝑆 = {𝑆0, 𝑆1, 𝑆2, 𝑆𝐹}
• 𝑆0= 𝑆0
• 𝛿 S0, a = S1
• 𝛿 S1, a = SF
• 𝛿 S1, b = S2
• 𝛿 S2, b = S1
• 𝐹 = {𝑆𝐹}
Bibliografia
 MENEZES, Paulo Blauth. Linguagens Formais e Autômatos.
Porto Alegre: Editora Sagra-Luzzatto, 1998;
 DIVERIO, Tiaraju Asmuz. Teoria da computação: maquinas
universais e computabilidade. Porto Alegre: Sagra Luzzatto,
2000;
 HOPCROFT, John. Introdução a teoria de autômatos,
linguagens e computação, trad. Vandenberg D. de Souza.
Rio de Janeiro: Elsevier, 2003.
Prof. Willian Magalhães 24