Aula 3 Autômatos Finitos Determinísticos

Prévia do material em texto

Linguagens Formais e 
Autômatos
Autômatos Finitos 
Determinísticos
Prof. Paulo
pfanio@gmail.com
Henrique
Adaptação do Material da Profª Débora Souza
Sistema de estados finitos
• Modelo matemático de sistemas com entradas e
saídas discretas.
• Assume um número finito e predefinido de estados.
• Todos os estados possíveis do sistema podem ser
explicitados antes de iniciar o processamento.
• Cada estado resume somente as informações do
passado necessárias para determinar as ações da
próxima entrada.
• Ex.: Lâmpada, elevador, etc.
Sistema de estados finitos
• Nem todos os sistemas de estados finitos podem
ser estudados por essa abordagem.
• Ex.: computador, cérebro, etc.
• Autômatos finitos e suas contrapartidas
probabilísticas cadeias de Markov são ferramenta
úteis no reconhecimento de padrões em dados.
• Usados em processamento de voz e reconhecimento de
caracteres ópticos e em, até mesmo, previsão de
mudanças de preço no mercado financeiro (cadeias de
Markov).
Introdução a autômato finito
O que é um computador???
Introdução ao autômato finito
• Máquina composta basicamente de três partes:
• Fita - entrada que contém a informação a ser
processada;
• Unidade de controle (UC) - possui uma unidade de
leitura (cabeça da fita) a qual acessa uma célula da fita
de cada vez. Movimenta-se exclusivamente para direita;
• Programa - também conhecido por função de transição,
comanda as leituras e define o estado da máquina.
Introdução ao autômato finito
• Características:
• A fita é dividida em pequenas partes chamadas de
células.
• Cada célula armazena um símbolo.
• A fita é finita, tanto a esquerda quanto a direita.
• Não é possível gravar sobre a fita.
• O tamanho da fita é o tamanho da entrada.
• A função de transição determina o novo estado do
autômato, dependendo do estado em que se encontra e
do símbolo lido.
• Para armazenar as informações passadas ao
processamento, usa-se o conceito de estado.
Autômato finito determinístico 
• Definição:
• “É uma máquina de estados finita que aceita ou rejeita
cadeias de símbolos gerando um único ramo de
computação para cada cadeia de entrada”.
Hopcroft, 2001
• Também é conhecido como autômato finito
determinístico (AFD).
• Cada modelo computacional permite criar
inúmeros “computadores abstratos”.
Autômato finito determinístico
• São bons modelos para máquinas com uma
pequena quantidade de memória.
• Podem modelar pequenos dispositivos como:
• Interruptor, porta automática, elevador.
• Ex. 1: autômato finito (diagrama de estados)
estado inicial
estado final
regra
transição
Autômato finito determinístico
• A função de transição pode ser representada como
um grafo finito direto.
• O processo de um AFD, para uma cadeia de
entrada, consiste na sucessiva aplicação da função
de transição para símbolo até ocorrer uma
condição de parada.
• De uma forma ou de outra o autômato sempre irá parar.
Autômato finito determinístico
• A parada pode acontecer de duas formas: aceitando ou
rejeitando a entrada.
• As condições de parada são:
• Após processar o último símbolo da fita, o autômato assume
um estado final: o autômato para e a entrada é aceita;
• Após processar o último símbolo da fita, o autômato assume
um estado não final: o autômato para e a entrada é rejeitada;
• A função de transição é indefinida para o argumento (estado
corrente e símbolo lido): a máquina para e a entrada é
rejeitada.
Autômato finito determinístico
0 10
cabeça da fita
fita
Função de transição como um grafo
• Ex. 1 (cont.):
• Dado a entrada 001, como seria o funcionamento
do autômato acima?
• Qual a função do autômato acima?
Autômato finito determinístico
• Ex. 2:
• O que podemos observar?
• O estado inicial é único.
• Pode-se ter mais de um estado final
• Quais cadeias podem ser aceitas pelo autômato
acima?
Definição formal de um autômato 
finito determinístico
• Diagramas de estado são mais fáceis de entender
intuitivamente.
• A definição formal se faz necessário por duas
razões:
• É precisa, ou seja, resolve quaisquer incertezas.
• Uma definição formal provê notação.
Definição formal de um autômato 
finito determinístico 
• Podemos definir matematicamente um autômato
finito determinístico D por meio uma quíntupla (ou
uma 5-upla):
D = (Q, ∑, δ, 𝑞0, F) 
• Onde:
• Q é um conjunto finito conhecido como estados
• ∑ é o alfabeto de símbolos de entrada
• δ é a função de transição. É do tipo: Q x ∑ → Q
• 𝒒𝟎 é o estado inicial (𝑞0 ∈ Q)
• F é o conjunto de estados de aceitação (F ⊆ Q)
Definição formal de um autômato 
finito determinístico
• Ex. 3:
• Podemos descrever M1 formalmente escrevendo M1 =
(Q, ∑, δ, 𝑞1, F), onde:
• Q = {q1, q2, q3}
• ∑ = {0, 1}
Definição formal de um autômato 
finito determinístico
• 𝑞1 é o estado inicial
• F = {q2}
• δ é descrita como:
0 1
q1 q1 q2
q2 q3 q2
q3 q3 q2
Definição formal de um autômato 
finito determinístico
• Ou como:
• δ(q1, 0) = q1
• δ(q1, 1) = q2
• δ(q2, 0) = q3
• δ(q2, 1) = q2
• δ(q3, 0) = q3
• δ(q3, 1) = q2
• M1 = ({q1, q2, q3}, {0, 1}, δ, q1, {q2})
Definição formal de um autômato 
finito determinístico
• Qual a definição formal dos autômatos
apresentados nos exemplos 1 e 2?
Autômato do exemplo 1 (M2)
Autômato do exemplo 2 (M3)
Definição formal de um autômato 
finito determinístico
• Definição formal do exemplo do 1:
M2 = ({q1, q2}, {0, 1}, δ, q1, {q2}), onde δ:
0 1
q1 q1 q2
q2 q2 q2
Definição formal de um autômato 
finito determinístico
• Definição formal do exemplo do 2:
M3 = ({q1, q2, q3, q4, q5}, {a, b}, δ, q1, {q2, q3}), 
onde δ:
a b
q1 q3 q2
q2 q5 q2
q3 q3 q4
q4 q3 q4
q5 q5 q2
Definição formal de computação
• Seja M = (Q, ∑, δ, 𝑞0, F) um AFD e suponha que 𝑤 =
𝑤1, 𝑤2, …𝑤𝑛 seja uma cadeia 𝑤𝑖 é membro de um
alfabeto ∑. Então M aceita w se existe uma sequencia
de estados 𝑟0, 𝑟1, … 𝑟𝑛 em Q com três condições:
1. 𝑟0 = 𝑞0
2. δ (𝑟𝑖, 𝑤𝑖 + 1) = 𝑟𝑖 + 1, para 𝑖 = 0, ..., 𝑛 – 1, e
3. 𝑟𝑛 ∈ F.
• Dizemos que M reconhece a linguagem A se A = {𝑤 | M
aceita 𝑤}.
• Uma linguagem é chamada de linguagem regular se
algum autômato finito a reconhece.
Projetando autômatos finitos 
determinísticos
• Ex. 4:
• Suponha que o alfabeto seja Σ = {0, 1} e que a linguagem
consista de todas as cadeias com um número ímpar de
1s.
• A construção do autômato finito para reconhecimento
dessa linguagem pode ser feita se perguntado coisas
como:
• Quais as possíveis entradas?
• Você precisa lembrar a cadeia inteira vista até então para
determinar se o número de 1s é ímpar?
• Quais são os estados?
• Qual o estado final ou o conjunto de estados de aceitação?
Projetando autômatos finitos 
determinísticos
• Cont. ex. 4:
Projetando autômatos finitos 
determinísticos
• Ex. 5:
• Criar um AFD para representar a linguagem L = {acaba},
definida sobre o alfabeto Σ = {a, b, c}.
Projetando autômatos finitos 
determinísticos
• Cont. ex. 5:
Projetando autômatos finitos 
determinísticos
• Ex. 6:
• Seja o alfabeto ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, construa
um AFD para a linguagem:
• {x ∈ ∑ | a sequência descrita por x corresponda a um valor
inteiro par}.
Projetando autômatos finitos 
determinísticos
• Ex. 7:
• Seja o alfabeto ∑ = {a, b}, construa um AFD para a
linguagem:
• {x ∈ ∑ | a sequência descrita por x possua subcadeia com dois
símbolos iguais}.