Compiladores: AFD

Compiladores
Conceitos Básicos
Professor: Cristiano Rodrigo Azevedo
Email: [email protected]
Sistema de estados finitos
 É uma máquina abstrata representada por:

 modelo matemático de um sistema com entradas e
saídas discretas.
 pode assumir um número pré-definido de estados.
 Cada estado resume somente informações do estado
passado para determinar as ações da próxima entrada.
Definição de Autômato Finito
 Interruptor
 Um interruptor comum tem dois estados possíveis:
ligado e desligado.
 Sobre esse interruptor podem ser realizadas duas
ações: ligar e desligar.
 O funcionamento deste interruptor pode ser descrito pelo
autómato finito seguinte:
Ligar
Iniciar
Desligado Ligado
Desligar
Exemplo de sistema de estados
finitos
 Um exemplo clássico e simples é o elevador.
 Trata-se de um sistema que não memoriza as requisições
anteriores.
 Cada “estado” sumariza as informações “andar corrente” e
“direção de movimento”.
 As entradas para o sistema são requisições pendentes.
 Exemplos, analisadores léxicos e alguns processadores de
texto, memorizam apenas a estrutura do prefixo das
palavras
Teoria dos Autômatos
 Autômatos finitos (AF):

 modelo restrito para o computador
 são dispositivos de reconhecimento de linguagens
 tem capacidade finita fixa de informação
 sem memória auxiliar
 sem saída de dados
 Pode-se dizer que é uma máquina abstrata que reconhece
linguagens.
 Supondo-se uma linguagem L e fornecendo ao AF uma
sequência de caracteres w, ele responderá se w  L ou w
 L.
Um autômato finito possui:

 Fita de entrada – armazena os símbolos da
cadeia de entrada;
 Controle finito - extrai símbolos da fita de
entrada através de um sensor de leitura;
 Função de transição – decide qual deverá ser o
próximo estado do autômato, com base no
símbolo lido e no estado anterior;
 Número finito de estados.
A Fita
 É finita a esquerda e a direita, dividida em

células onde cada uma armazena um símbolo.
 Não é possível gravar sobre a fita e não existe
memória auxiliar
 Inicialmente a cadeia a ser processada ocupa
toda fita
Unidade de controle
 Possui um número finito de estados pré-definido.

 A unidade lê um símbolo da fita de cada vez e
move a cabeça para a direita
 Inicialmente a cabeça é posicionada mais a
esquerda da fita.
 Importante – O autômato Finito não possui
memória de trabalho.
Autômatos finitos equivalentes
 Dois autômatos finitos M1 e M2 são ditos equivalente se, e

somente se:
 ACEITAM(M1) = ACEITAM(M2)
 Uma linguagem aceita por um autômato finito

determinístico é uma linguagem regular
Graficamente um AF pode ser representado por
fita com a cadeia w de entrada
a a b b
Cabeça
de leitura
Início do processo
Controle
de reconhecimento
Finito
pelo estado inicial qo
Um autômato finito reconhece uma

linguagem regular!
 A utilização do termo “determinístico” para designar esse

tipo de autômato finito decorre do fato de que, enquanto
houver símbolos na fita de entrada, será sempre possível
determinar o estado seguinte a ser assumido pelo
autômato, o qual será único em todas as situações.
Determinístico
 Autômato finito M sobre um alfabeto Σ é uma quíntupla
(Q, Σ, δ, q0, F), onde:
1. Q é o conjunto finito de estados
2. Σ é o alfabeto dos símbolos da linguagem

3. δ : Q x Σ →Q é a função de transição de estados
4. q0 é o estado inicial
5. F é o conjunto de estados finais
 δ é uma função parcial, pois não precisa estar definida
para todos os pares Q x Σ Interesse: há equivalência entre
AF e ER
Determinístico
 A máquina de estados de um autômato finito, também
denominada controle finito, é definida pelo conjunto de
estados Q e pela função de transição δ, que associa pares
ordenados do tipo:
 estado corrente
 entrada corrente
 Com um novo estado a ser assumido pelo autômato
quando da aplicação da transição.
Determinístico
 A função de transição δ pode ser, no caso dos autômatos
finitos determinísticos, uma função total, ou seja, uma
função que é definida para todos os elementos de Q×Σ, ou
ainda uma função parcial.
 Se total, isso implica a especificação de transições com
cada um dos possíveis símbolos de entrada σ ∈ Σ para
cada um dos possíveis estados q ∈ Q do autômato finito.
 Assim, se |Σ| = m e |Q| = n, então o autômato finito
determinístico possuirá, exatamente, m ∗ n transições
distintas.
Determinístico
 As transições de um autômato finito podem ser denotadas
através de expressões do tipo:
 (p,σ) → q, com p,q ∈ Q, σ ∈ Σ.
 Uma alternativa, pode-se explicitar a função δ,
representando uma transição na forma δ(p,σ) = q
Determinístico
 A configuração de um autômato finito é definida pelo seu

estado corrente e pela parte da cadeia de entrada ainda
não analisada (incluindo o símbolo apontado pelo cursor).
 A configuração inicial de um autômato finito é aquela em

que o estado corrente é q0 (estado inicial) e o cursor de
leitura se encontra posicionado sobre o símbolo mais à
esquerda da cadeia de entrada.
Determinístico
 Uma configuração final é aquela em que o cursor aponta
para a posição imediatamente além do último símbolo da
cadeia (indicando com isso já ter ocorrido a leitura do
último símbolo da cadeia de entrada), e o estado corrente
pertence ao conjunto F de estados finais, especificado para
o autômato.
 Note que ambas as condições devem ser simultaneamente
verificadas para permitir a caracterização de uma
configuração como sendo, respectivamente, inicial ou final.
Determinístico
 Quando ocorre o esgotamento da cadeia de entrada, deve-
se analisar o tipo do estado corrente do autômato.
 Estado final: diz-se que o autômato reconheceu, ou
aceitou, a cadeia de entrada.
 Estado não-final: diz-se que a cadeia de entrada foi
rejeitada pelo autômato, logo a cadeia analisada não
pertence à linguagem por ele definida.
Precedência dos operadores
1. Símbolo ( * ) – Fecho recursivo e transitivo (maior)
2. Símbolo ( . ) – Concatenação
3. Símbolo ( ∪ ) – União (menor)
Linguagem reconhecida
 A linguagem L definida por um autômato finito M é o

conjunto de todas as cadeias ( w ) sobre o alfabeto Σ que
levam M da sua configuração inicial para alguma
configuração final através da aplicação sucessiva de
transições definidas pela função δ.
 Denota-se como:
L(M) = {w ∈ Σ∗| (q0,w) ⊢∗ (qF,ε), qF ∈ F}

Exemplo de autômato finito
Determinístico
Tabela de estados
0
Estado Atual  0 1 q0 q1
Estado 0
q0 q1 q2
Inicial
q1 q0 q2 1 1
Estado
Final
q2 q2 q2 q2
0,1
Exercício 1
 Construir a tabela de estados e o AFD que

reconhece a linguagem a*.
Estado Atual  a a
Estado inicial q0 q0
Estado final q0 q0 q0
Exercício 2

reconhece a linguagem aa*.
Estado Atual  a
Estado inicial q0 q1
Estado final q1 q1 a a
qo q1
Exercício 3

reconhece a linguagem (abb*a)*
Estado Atual  a b
Estado
q0 q1 𝜀 a
inicial
q1 𝜀 q2
q2 q0 q2 qo b q1
Estado final q0 q1 𝜀 b
a
q2
Exercício 4
 Construir um AFD que reconheça a palavra-chave web

 O AFN abaixo reconhece a palavra-chave web
Exercício 4 – solução
 Construir um AFD que reconheça a palavra-chave web

 O AFN abaixo reconhece a palavra-chave web
w e b
q0 q1 q2 q3
Exercício 5
Construir a tabela de estados e o AFD que reconheça uma

quantidade ímpares de 1s, tendo como alfabeto {0,1}.
Cadeias reconhecidas:
a. 1
b. 001
c. 010101
d. 10101
e. 010010 Não reconhecida
Construir a tabela de estados e o AFD que reconheça uma

quantidade ímpares de 1s, tendo como alfabeto {0,1}.
Cadeias reconhecidas: Estado 0 1

Atual 
a. 1 Estado
q0 q0 q1
inicial
b. 001 Estado
q1 q1 q0
final
c. 010101
0 0
d. 10101
Não
1
e. 010010 reconhecida q0 q1
1
Exercício 6
Construa a função do AFD M que reconheça uma quantidade

impares de 1s, tendo como alfabeto {0,1}.
0 0
1
q0 q1
1
Construa a função do AFD M que reconheça uma quantidade

impares de 1s, tendo como alfabeto {0,1}.
M = (Q, ∑, , q0, F)
0 0 Q = {q0, q1 }
∑ = { 0, 1 }
1
q0 = q0
q0 q1 F = { q1 }
1 δ : Q x Σ →Q
(q0,0)=q0, (q0,1)=q1
(q1,0)=q1, (q1,1)=q0
Exercício 7
 Construa um AFD M que reconheça qualquer w que
termine com 10, tendo como ∑ {0,1}.
 Construa um AFD M que reconheça qualquer w que
termine com 10, tendo como ∑ {0,1}.
0
1
0 q1 q3
1
q0 0
1 0
0
q2 q5
1 1 0
1
q4
Exercício 8
 Construa um AFD M que reconheça qualquer w com

números pares de zeros (0) e uns (1), tendo como ∑ {0,1}.
 Construa um AFD M que reconheça qualquer w com

números pares de zeros (0) e uns (1), tendo como ∑ {0,1}.
1
q0 q1
1
0 0 0 0
1
q2 q3
1
Exercício 9
 Construa um AFD M que reconheça qualquer w que se

tiver (0), deva ser em par de zeros (0), tendo como ∑ {0,1}.
 Construa um AFD M que reconheça qualquer w que se

tiver (0), deva ser em par de zeros (0), tendo como ∑ {0,1}.
1
1
q1
q0
0 0
0 0 1
q2 1 q3
Exercício 10
 Construir um AFD M para reconhecer as cadeias formadas

por um número arbitrário de repetições de 1 a 3 a's
seguidos pelo mesmo número de b's.
 Exemplo da L(M) = (ab|aabb|aaabbb)*

Compiladores: AFD

Enviado por

Direitos autorais:

Formatos disponíveis

Compiladores: AFD

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Compiladores: AFD

Enviado por

Direitos autorais:

Formatos disponíveis

Compiladores

Professor: Cristiano Rodrigo Azevedo

 É uma máquina abstrata representada por:

 Autômatos finitos (AF):

Um autômato finito possui:

 É finita a esquerda e a direita, dividida em

 Possui um número finito de estados pré-definido.

 Dois autômatos finitos M1 e M2 são ditos equivalente se, e

 Uma linguagem aceita por um autômato finito

Graficamente um AF pode ser representado por

fita com a cadeia w de entrada

Um autômato finito reconhece uma

 A utilização do termo “determinístico” para designar esse

2. Σ é o alfabeto dos símbolos da linguagem

 A configuração de um autômato finito é definida pelo seu

 A configuração inicial de um autômato finito é aquela em

1. Símbolo ( * ) – Fecho recursivo e transitivo (maior)

 A linguagem L definida por um autômato finito M é o

L(M) = {w ∈ Σ∗| (q0,w) ⊢∗ (qF,ε), qF ∈ F}

 Construir a tabela de estados e o AFD que

 Construir a tabela de estados e o AFD que

 Construir a tabela de estados e o AFD que

 Construir um AFD que reconheça a palavra-chave web

 Construir um AFD que reconheça a palavra-chave web

Construir a tabela de estados e o AFD que reconheça uma

Construir a tabela de estados e o AFD que reconheça uma

Cadeias reconhecidas: Estado 0 1

Construa a função do AFD M que reconheça uma quantidade

Construa a função do AFD M que reconheça uma quantidade

 Construa um AFD M que reconheça qualquer w com

 Construa um AFD M que reconheça qualquer w com

 Construa um AFD M que reconheça qualquer w que se

 Construa um AFD M que reconheça qualquer w que se

 Construir um AFD M para reconhecer as cadeias formadas

Você também pode gostar