Autômatos Finitos Determinísticos

Prévia do material em texto

AUTÔMATOS FINITOS 
DETERMINÍSTICOS 
Marcelo Guerra 
INTRODUÇÃO 
 Linguagens formais são mecanismos formais para 
representação e especificação de linguagens, baseados na 
chamada Teoria da Computação. 
 
 As representações podem ser feitas por: 
 
 Reconhecedores: dispositivos formais que servem para 
verificar se uma sentença pertence ou não à determinada 
linguagem 
 Autômatos. 
 
 Geradores: dispositivos formais que permitem a geração 
sistemática de todas as sentenças de uma linguagem. 
 Gramáticas. 
DEFINIÇÃO INFORMAL DE AUTÔMATO 
 Reconhecedor de cadeias de uma dada 
linguagem. 
 
 É um programa que toma como entrada uma 
cadeia x e responde “sim” se x for uma sentença 
da linguagem e “não”, caso contrário. 
EXEMPLO: AUTÔMATO FINITO 
 O seguinte autômato modela um interruptor 
Desligado Ligado Início 
Pressionar 
Pressionar 
DEFINIÇÃO INFORMAL 
 Os estados são representados por círculos. 
 No exemplo, denominados “ligado” e “desligado”. 
 
 Arcos são rotulados com alguma “entrada”. 
 “Pressionar” indica que um usuário, exterior ao 
sistema, acionou o botão. 
 
 Estado inicial: por convenção, usaremos uma seta 
que chega neste estado rotulada por “início”. 
 
 Um estado final indica que uma sequência de 
entradas é válida, ou aceita. 
 Notação: dois círculos concêntricos. 
 
EXEMPLO: RECONHECIMENTO DE CADEIAS 
t th the then 
Início t h e n 
AUTÔMATOS FINITOS 
DETERMINÍSTICOS 
INTRODUÇÃO 
 Autômato Determinístico: existe apenas um 
estado para o qual ele pode transitar a partir do 
estado atual, dada uma certa entrada. 
 
 Não-determinístico: pode se encontrar em vários 
estados ao mesmo tempo. 
 
 Nomenclatura: “Autômato finito”, quando não 
especificado, se refere à variedade determinística 
(DFA ou AFD). 
DEFINIÇÃO 
 Um autômato Finito Determinístico consiste em: 
 
1. Q - Um conjunto finito de estados. 
 
2. Σ - Um conjunto finito de símbolos de entrada. 
 
3. δ (q,a) - Uma função de transição, que toma um estado e 
um símbolo de entrada e retorna um estado. 
 Se q é um estado e a é um símbolo de entrada, então 
δ(q,a) = p , indica que existe um arco rotulado a de q para p. 
 
4. q0 ∈ Q - o estado inicial. 
 
5. F ⊆Q - um conjunto de estados finais ou de aceitação.
 
 
DEFINIÇÃO(CONT.) 
 
 Um AFD pode ser representado pela listagem 
dos seus componentes da seguinte maneira: 
 
A = (Q, Σ, δ, q0, F) 
PROCESSAMENTO DE STRINGS 
 Um AFD aceita ou não uma cadeia de símbolos 
de entrada. 
 
 A linguagem de um AFD é o conjunto de todas as 
palavras que ele aceita. 
PROCESSAMENTO DE STRINGS 
 Suponha que a1,a2,…,an seja uma seqüência de símbolos de 
entrada. 
 
 O AFD começa em seu estado inicial q0. 
 
 Aplicamos a função de transição δ(q0, a1) cujo resultado é, 
digamos, q1. 
 
 Em seguida aplicamos δ sobre q1 e a2, obtendo o próximo estado, e 
assim por diante. Se o último estado qn é um elemento de F, então 
a entrada é aceita. 
 
 Caso contrário, a palavra é rejeitada. 
 
q0 q1 q2 
a1 a2 … qn 
δ(qi-1 , ai) = qi 
EXEMPLO 
 O autômato que aceita todas e somente as strings de 0’s 
e 1’s que têm a seqüência 01 em algum lugar na string. 
 
 L = {w | w é da forma x01y para quaisquer strings x e y que 
consistem somente de 0’s e 1’s} 
 L = {x01y | x e y quaisquer strings de 0’s e 1’s} 
 Exemplos: 
• Pertencem a L 
• 01 
• 11010 
• 100011 
 
 
• Não pertencem a L 
• ε 
• 0 
• 111000 
EXEMPLO - CRIAÇÃO DO AUTÔMATO 
 Σ = {0,1}. 
 Para decidir se 01 é uma substring da entrada, o 
autômato precisa “lembrar”: 
 
1. Se 01 já foi vista, então qualquer seqüência adicional de 
símbolos deve ser aceita. 
 
2. Se 01 ainda não foi lida, mas 0 foi a última entrada: se a 
próxima entrada for 1, então ele pode ler qualquer 
cadeia em seguida. 
 
3. Se 01 não foi lido ainda, mas sua última entrada foi 
nula, ou foi 1, então não deve aceitar a cadeia, até ver 
um 0 seguido de 1. 
 
Cada uma dessas 3 condições pode ser representada por um 
estado. 
ESTADOS E TRANSIÇÕES I 
 A condição (3) é representada pelo estado inicial 
q0 - se virmos um 1 neste estado, não deveremos 
avançar. Assim, temos δ(q0 , 1) = q0. 
 
 Se estamos em q0 e em seguida virmos um 0, 
estamos na condição (2), estado representado por 
q2 : δ(q0 , 0) = q2. 
ESTADOS E TRANSIÇÕES II 
 Se estamos em q2 e virmos um 0, nossa situação não 
muda. Então, devemos continuar em q2 : δ(q2 , 0) = q2. 
 
 Se estamos em q2 quando lermos um 1, então temos a 
substring. Podemos, portanto, ir a um estado de 
aceitação : δ(q2 , 1) = q1 (condição (1)). 
 
 Em q1 a seqüência 01 já foi lida. Independentemente do 
restante da entrada, devemos aceitá-la. Assim, 
δ(q1 , 0) = δ(q1 , 1) = q1. 
 
AUTÔMATO FINAL 
 
 Q = {q0 , q1 , q2 }. 
 q0 é o estado inicial. 
 Σ = {0,1}. 
 δ é definida por 
 δ(q0 , 1) = q0 
 δ(q0 , 0) = q2 
 δ(q2 , 0) = q2 
 δ(q2 , 1) = q1 
 δ(q1 , 0) = δ(q1 , 1) = q1 
 F={q1}. 
 
 
 
 
REPRESENTAÇÕES 
 Há duas notações mais intuitivas para 
autômatos: 
 Diagramas de transição. 
 Tabela de transições – uma listagem tabular da 
função δ. 
DIAGRAMA DE TRANSIÇÕES 
 Um diagrama de transições para o AFD A = (Q, Σ, δ, q0, 
F) é um grafo definido como segue: 
 
a) Para cada estado em Q existe um nó correspondente. 
 
b) Para cada q ∈ Q e a ∈ Σ, seja δ(q, a) = p. Então o diagrama 
tem um arco rotulado a de q até p. 
 Se existem vários símbolos com a transição de q para p, o arco 
será rotulado com todos eles. 
 
c) Existe uma seta no estado inicial rotulada início que não tem 
nó de origem. 
 
d) Os nós correspondentes aos elementos de F são marcados por 
um círculo duplo. 
EXEMPLO 
 
q0 q2 q1 
0 1 Início 
1 0 0,1 
TABELAS DE TRANSIÇÃO 
 É uma representação convencional e tabular de 
uma função que recebe dois argumentos e retorna 
um valor. 
 As linhas correspondem aos estados e as colunas 
às entradas. 
 Exemplo: 
 0 1 
→q0 q2 q0 
 *q1 q1 q1 
 q2 q2 q1 
ESTENDENDO A FUNÇÃO DE TRANSIÇÃO 
AOS STRINGS 
 Um AFD define uma linguagem L: 
 
 L é o conjunto de todas as cadeias que resultam em 
uma seqüência de transições que levam o autômato 
do estado inicial a um dos estados de aceitação. 
 
 No diagrama de transições, L é o conjunto de rótulos 
ao longo de todos os caminhos que levam do estado 
inicial a qualquer estado de aceitação. 
FUNCÃO DE TRANSIÇÃO ESTENDIDA 
 Descreve o que acontece quando começamos em 
qualquer estado e seguimos qualquer seqüência 
de entradas. 
 
 Se δ é a função de transição, δ* é a função 
estendida que toma um estado q e uma string w e 
retorna um estado p. 
 
 p é o estado que o autômato alcança a partir do 
estado q e processa a seqüência de entradas w. 
FUNCÃO DE TRANSIÇÃO ESTENDIDA 
 Definimos δ* por indução sobre o comprimento da 
string de entrada como segue: 
 
1. Base: δ*(q, ε) = q. 
 
2. Indução: suponha que w seja uma string da 
forma xa (a é o último símbolo de w), então: 
 δ*(q, w) = δ (δ*(q, x), a). 
 
EXEMPLO 
 Projetar um AFD para aceitar a linguagem 
 L = {w | w tem ao mesmo tempo um número par de 
0’s e um número par de 1’s}. 
 
 A função do autômato é lembrar se o número de 
0’s lido até certo momento é par ou ímpar (idem 
para os 1’s). 
 
 Existem 4 estados: 
 q0: O número de 0’s vistos até agora e de 1’s é par 
 q1: O número de 0’s épar e o de 1’s é ímpar 
 q2: O número de 0’s é ímpar e o de 1’s é par 
 q3: O número de 0’s e 1’s vistos é ímpar 
 
EXEMPLO (CONT) 
 O estado q0 é o estado 
inicial e ao mesmo 
tempo o único estado 
de aceitação. 
 Antes de ler qualquer 
entrada, o número de 
0’s e 1’s é par. 
 
q1 
q2 
Início 
q0 
q3 
EXEMPLO (CONT) 
 No estado q0, ao 
lermos um 1 da 
entrada, o número de 
1’s passa a ser ímpar 
 Passamos para q1 
 
 Ao recebermos outro 1 
como entrada, 
voltamos a equilibrar 
o número de 1’s 
 Retornamos a q0 
 
q1 
q2 
Início 
q0 
q3 
1 
1 
EXEMPLO (CONT) 
 No estado q0, ao 
lermos um 0 da 
entrada, o número de 
0’s passa a ser ímpar. 
 Passamos para q2. 
 
 Ao recebermos outro 0 
como entrada, 
voltamos a equilibrar 
o número de 0’s. 
 Retornamos a q0. 
 
q1 
q2 
Início 
q0 
q3 
1 
1 
0 0 
EXEMPLO (CONT) 
 Em q1, o número de 
1’s é ímpar e o de 0’s é 
par. 
 
 Em q3, ambas as 
quantidades são 
ímpares. 
 
q1 
q2 
Início 
q0 
q3 
1 
1 
0 0 1 
1 
0 
0 
VERIFICAÇÃO DAS ENTRADAS 
 Vejamos a computação de 
δ*(q0, w) para cada prefixo 
w de 110101: 
 δ*(q0, ε) = q0 
 
 δ*(q0, 1) = δ (δ*(q0, ε),1) = 
δ (q0 , 1) = q1 
 
 δ*(q0, 11) = δ (δ*(q0, 1),1) = 
δ (q1 , 1) = q0 
 
 δ*(q0, 110) = δ (δ*(q0, 11),0) = 
δ (q0 , 0) = q2 
 
 … 
q1 
q2 
Início 
q0 
q3 
1 
1 
0 0 1 
1 
0 
0 
A LINGUAGEM DE UM AFD 
 A linguagem de um AFD A = (Q, Σ, δ, q0, F), 
denotada por L(A) é definida por 
 L(A) = { w | δ*(q0, w) ∈ F} 
 
 Se L é o L(A) para algum AFD A, então dizemos 
que L é uma linguagem regular. 
EXERCÍCIO 
 Represente o AFD M = {{q0, q1, q2}, {0, 1}, δ, q0, 
{q1}}, onde δ é dado por 
 δ(q0, 0) = q0, δ(q0, 1) = q1 
 δ(q1, 0) = q0, δ(q1, 1) = q2 
 δ(q2, 0) = q2, δ(q2, 1) = q1. 
 
EXERCÍCIOS 
 Proponha AFDs que aceitem as linguagens a 
seguir: 
 Todas as cadeias sobre Σ = {0,1} que terminem 
em 01. 
 Todas as cadeias, sobre Σ = {a,b} , com prefixo 
ab. 
 L(M)={x ∈ {0,1}* | x tenha dois zeros 
consecutivos ou dois uns consecutivos.} 
 Escreva uma tabela de transição para o autômato 
que reconhece a linguagem abaixo: 
 L = {w {0,1}* | w tem ao mesmo tempo um número 
par de 0’s e um número par de 1’s} 
 
 
 
 
GABARITO 
q0 q1 q2 
a b 
a,b 
q3 
b 
a 
a,b 
q0 q1 q2 
0 0 
0,1 
q3 
1 
q4 0,1 
1 0 
1 
q0 q1 q2 
0 1 
1 0 
0 
1 
GABARITO 
0 1 
→*q0 q2 q1 
 q1 q3 Q0 
 q2 q0 Q3 
q3 q1 q2 
q1 
q2 
Início 
q0 
q3 
1 
1 
0 0 1 
1 
0 
0