Linguagens Formais e Autômatos - Leandro Dionízio - Aula 02 AFD

Prévia do material em texto

Linguagens Formais
Leandro Dionízio Ramos
1
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 palavras
• Denotacional (Gerador?)
Uma expressão que denota de modo geral as 
palavras da linguagem
2
Modelos de Máquinas
• Dispositivo Reconhecedor. 
Uma maneira de definir uma linguagem é 
através da utilização de um dispositivo 
reconhecedor, que permite submeter uma 
palavra ou cadeia a um teste de aceitação 
capaz de determinar se tal palavra pertence 
ou não à linguagem em questão.
3
Modelos de Máquinas
• Dispositivo Reconhecedor.
O dispositivo reconhecedor é na verdade um 
modelo matemático que descreve o 
funcionamento de uma máquina, onde as 
cadeias são submetidas para aceitação ou 
rejeição.
4
Autômato Finito
• Um autômato é um modelo abstrato de um 
computador digital composto:
– por entrada (que conterá a cadeia de entrada);
– uma saída (para mostrar a cadeia resultante);
– memória auxiliar (que armazena temporariamente 
símbolos do alfabeto);
– unidade de controle.
5
Autômato Finito
• Um autômato finito é o modelo 
computacional mais simples e pode ser 
chamado, também, de máquina de estados 
finitos.
6
Autômato Finito
• Tomando como exemplo a porta automática 
(presente em supermercados, shoppings, 
etc.), podemos observar na Figura que existe 
um tapete na frente da porta e outro tapete 
atrás.
7
Autômato Finito
• Ambos os tapetes detectam a presença de 
pessoas prestes a atravessar a passagem, 
abrindo a porta quando alguém se aproxima e 
mantendo-a aberta até que a pessoa se afaste.
8
Autômato Finito
• O controlador pode estar em dois estados (aberto 
ou fechado) e passa de um estado para outro 
dependendo do estímulo (entrada) que recebe. 
Nesse caso, tem-se 4 estímulos diferentes:
– frente (uma pessoa está no tapete da frente);
– retaguarda (uma pessoa está no tapete de dentro); 
– ambos (há pessoas sobre os dois tapetes);
– nenhum (não há ninguém sobre os tapetes).
9
Autômato Finito
• Para cada estímulo, o controlador vai responder de 
uma forma diferente, realizando as transições de um 
estado para outro. A representação das possíveis 
transições de acordo com cada estímulo (chamamos 
essa representação de diagrama de estados).
10
Autômato Finito
• Tabela de transição:
11
Autômato Finito
• Ao receber a sequência de estímulos frente; 
retaguarda; nenhum; frente; ambos.
Tem-se as seguintes transições:
– fechado (início) -> aberto; aberto -> aberto; aberto -> 
fechado; fechado -> aberto; aberto -> aberto.
12
Autômato Finito
• Exemplo de Interruptor
– Estados Desligado e Ligado:
Tabela de Transição
13
Pressionar
Desligado Ligado
Ligado Desligado
Autômato Finito
• Exemplos: 
Estados q0, q1, q2, q3, q4:
– Qualquer palavra que não seja ( amor ) deve ser descartada.
Tabela de Transição
14
a m o r
q0 q1 - - -
q1 - q2 - -
q2 - - q3 -
q3 - - - q4
q4
Autômato Finito
15
Autômato Finito
• Outro exemplo
Estados s1 e s2:
Tabela de Transição
16
1 0
s1 s1 s2
s2 s2 s1
Autômato Finito
• O autômato finito pode ser determinístico 
(AFD) e não determinístico (AFN). 
• No AFD cada movimento é determinado de 
uma única forma, enquanto que no AFN 
existem várias possibilidades de transição para 
um mesmo símbolo.
17
Autômato Finito
• Formalismo reconhecedor
– Recebe uma palavra de entrada
– Indica se ela é aceita ou rejeitada
• Baseado no conceito de “máquinas de estados 
finitas”
18
Autômato Finito Determinístico (AFD)
• Um Autômato Finito Determinístico (AFD) é 
um modelo de máquina definido formalmente 
por uma quíntupla M = (Σ, Q, δ , q0, F).
19
Autômato Finito Determinístico (AFD)
• Quíntupla M = (Σ, Q, δ , q0, F):
– Σ: alfabeto de símbolos de entrada
– Q: conjunto finito de estados possíveis para M
– δ (beta): função transição ou função programa 
definida em Q x Σ = Q
– q0: estado inicial de M, sendo (q0 ∈ Q)
– F: conjunto de estados finais, tal que (F ∈ Q)
20
Autômato Finito Determinístico (AFD)
21
Autômato Finito Determinístico (AFD)
22
• Definir um AFD engloba definir
– Um conjunto finito de estados;
– Um alfabeto de entrada que indica os símbolos de 
entrada permitidos;
– Um conjunto de regras de movimento que indicam 
como ir de um estado p/ outro, dependendo do 
símbolo de entrada;
– Um estado escolhido como estado inicial;
– Um conjunto de estados escolhidos como estados 
finais (de reconhecimento);
Autômato Finito Determinístico (AFD)
23
• A máquina inicia sua execução em um estado 
inicial, a partir do primeiro símbolo da palavra
– Estado inicial é único
• Ao final, a máquina deve terminar em um 
estado final para a palavra ser reconhecida
– O número de estados finais é livre
Autômato Finito Determinístico (AFD)
24
• Um autômato finito M1: (diagrama de estados)
• M1 tem 3 estados, q1, q2, q3 ;
• M1 inicia no estado q1 ;
• M1 tem um estado final, q2 ;
• Os arcos que vão de um estado p/ outro chamam-se 
transições.
Autômato Finito Determinístico (AFD)
25
• O autômato finito M1 recebe os símbolos de entrada 
um por um;
• Depois de ler cada símbolo, M1 move-se de um 
estado para outro, de acordo com a transição que 
possui aquele símbolo como seu rótulo;
• Quando M1 lê o ultimo símbolo ele produz uma 
saída:
– reconhece se M1 está 
no estado final
– não-reconhece se M1 
não estiver.
Autômato Finito Determinístico (AFD)
26
• Exemplo: entrada 1101
1. Inicia no estado q1.
2. Lê 1, segue transição de q1 p/ q2.
3. Lê 1, segue transição de q2 p/ q2.
4. Lê 0, segue transição de q2 p/ q3.
5. Lê 1, segue transição de q3 p/ q2.
6. Pára c/ saída reconhece.
Autômato Finito Determinístico (AFD)
27
• Vamos testar as entradas: 1, 01, 11, 0101 (em M1)
Percebemos que :
- M1 reconhece qualquer cadeia que termine 
com 1 (vai p/ o estado final q2 toda vez que lê 
1);
- M1 não reconhece cadeias como 0, 10, 
101000.
Autômato Finito Determinístico (AFD)
28
• Desenvolva um Autômato que reconhece a linguagem de 
números binários com quantidade ímpar de 1s.
• M = (Σ, Q, δ , q0, F): 
• Σ = ({ 0, 1 }, Q = { qpar, qimpar }, q0 = { qpar }, F = { qimpar })
Autômato Finito Determinístico (AFD)
29
• Um Autômato Finito nunca entra em “loop” infinito
• Novos símbolos da entrada são lidos a cada aplicação da 
função programa, o processo de reconhecimento de qualquer 
cadeia finaliza de duas maneiras:
– Aceitando ou;
– rejeitando uma entrada.
Autômato Finito Determinístico (AFD)
30
• Praticando:
De acordo com a sequência de estados pelos quais passa o 
AFD M dado abaixo quando recebe como entrada a palavra 
01010. Diga se a palavra é aceita ou rejeitada e justifique.
• A = ({0,1}, {q0, q1, q2, q3}, δA, q0, {q3}), onde δA é dado 
abaixo: