Autômatos Finitos e Linguagens Regulares

Prévia do material em texto

INE5317 
Linguagens Formais e 
Compiladores
Ricardo Azambuja Silveira
INE-CTC-UFSC
E-Mail: silveira@inf.ufsc.br
URL: www.inf.ufsc.br/~silveira
AULA 5: Autômatos Finitos
06/09/06 Ricardo Silveira 2
As Linguagens e os formalismos 
representacionais
● Os tipos de formalismos utilizados:
– Denotacional: as linguagens são representadas 
por meio de uma função que caracteriza o 
conjunto de palavras admissíveis na linguagem
● EXPRESSÕES REGULARES
– Axiomático: as linguagens são representadas 
através de regras que constituem uma Gramática 
que permite derivar todo o conjunto de sentenças
● GRAMÁTICAS
– Operacional: as linguagens são representadas 
por máquinas abstratas ou autômatos, baseados 
em estados, em instruções primitivas e em como 
cada símbolo modifica cada estado
● AUTÔMATOS
06/09/06 Ricardo Silveira 3
Sistemas de Estados Finitos
● Um Sistema de Estados Finitos é um modelo 
matemático de sistemas com entradas e saídas 
discretas que pode assumir um número finito e 
pré-definido de estados
● Cada estado resume somente as informações 
do passado necessárias para determinar as 
ações para a próxima entrada
06/09/06 Ricardo Silveira 4
Tipos de autômatos
● Autômato finito
● Autômato com pilha
● Máquina de Turing com fita finita
● Máquina de Turing
06/09/06 Ricardo Silveira 518
LINGUAGENS REGULARES 
E AUTÔMATOS FINITOS
● Constituem um conjunto de linguagens 
decidíveis bastante simples e com propriedades 
bem definidas e compreendidas. 
● Podem ser reconhecidas por Autômatos Finitos 
e são facilmente descritas por expressões 
simples, chamadas Expressões Regulares. 
● Podem ser abordadas através de fomalismos:
– Operacional ou reconhecedor: Autômato Finito 
(Determinístico e Não-determinístico e Vazio).
– Axiomático ou gerador: Gramática Regular
– Denotacional: Expressão Regular
06/09/06 Ricardo Silveira 620
Autômato Finito
● Um Autômato Finito é um reconhecedor de 
L.R.
– Entende-se por reconhecedor de uma linguagem 
L um dispositivo que tomando uma seqüência w 
como entrada, responde “sim” se w ∈ L e “não” 
caso contrário. 
● Os Autômatos Finitos classificam-se em:
– Autômatos Finitos Determinísticos (AFD)
– Autômatos Finitos Não-Determinísticos (AFND)
– Autômatos Finitos com Movimentos Vazios (AFε)
06/09/06 Ricardo Silveira 7
Autômato Finito Determinístico
● Um autômato finito determinístico é uma 
máquina abstata composta por:
– Fita
● Dispositivo de entrada que contém a 
informação a ser processada
– Unidade de controle
● Reflete o estado corrente da máquina. Possui 
uma leitora que lê uma célula de cada vez e 
movimenta-se para a direita
– Programa ou Função de Transição
● Comanda as leituras e define o estado da 
máquina
06/09/06 Ricardo Silveira 8
Autômato Finito Determinístico
● Um autômato finito 
determinístico (AFD)é uma 5-
upla:
– M= (Q, Σ, δ, q0,F)
– Q é um conjunto de estados 
possíveis do autômato, o qual é 
finito;
– Σ é um alfabeto de símbolos de 
entrada; 
– δ (delta) é um programa ou 
função de transição: δ:Q × Σ → 
Q
– q0 é o estado inicial, tal que q0 é 
elemento de Q
– F é o conjunto de estados 
a a b c c b a a
Controle
06/09/06 Ricardo Silveira 9
Função de transição
δ(q; a) = p 
para q, p ∈ K e 
a ∈ Σ, 
significando que, estando no estado q e lendo o 
síımbolo a na fita de entrada, o autômato muda 
para o estado p e avança o cabeçote uma posição.
06/09/06 Ricardo Silveira 1021
M= (Σ, Q, δ, q0,F)
∑ alfabeto de símbolos de entrada; 
Q conjunto de estados possíveis do autômato, o qual é finito;
δ programa ou função de transição: δ: Q x ∑ → Q
q0 estado inicial, tal que q0 é elemento de Q (indicado por uma seta)
 F conjunto de estados finais, tal que F está contido em Q;
a
estado anterior novo estado
p q
símbolo lido
Represertação de autômato 
como grafo
06/09/06 Ricardo Silveira 11
Exemplo
● M = ({q0, q1, q2}, {a; b}, δ, q0, {q2}),
– δ(q0; a) = q1,
– δ(q1; a) = q1, 
– δ(q1; b) = q2.
– Logo, T(M) = {anb | n ≥ 1 }.
06/09/06 Ricardo Silveira 12
Tabela de transição de 
estados
● Uma terceira forma de representar um AF:
– Tabela indicando na vertical os estados, e na 
horizontal os síımbolos do alfabeto. 
– No cruzamento estão as transições possíveis;
– O estado inicial é indicado por uma seta, e os 
estados finais por asteriscos.
δ a b
→q0 q1 -
q1 q1 q2
*q2 - -
06/09/06 Ricardo Silveira 13
 δ a b
q0 q1 q2
q1 qf q2
q2 q1 qf
qf qf qf
q0
q2q1
qf
a b
b
a,b
a
a
b
δ1 é representada na tabela
Exemplo de AFD
– Considere a linguagem:L1={w | w possui aa ou bb 
como subpalavra}
● AF: M1=({a,b},{q0,q1,q2,qf}, δ
1
, q0, {qf})
06/09/06 Ricardo Silveira 14
 δ 0 1
→*q0 q0 q1
*q1 q0 -
0
1
δ1 é representada na tabela
Exemplo de AFD
– Considere a linguagemconstituída por sentenças 
em {0; 1}* as quais não contém dois ou mais 1’s 
consecutivos
● AF: M1=({0,1},{q0,q1}, δ, q0, {q0,q1})
● δ(q0; 0) = q0, δ(q0; 1) = q1, δ(q1; 0) = q0.
0
q1q0
06/09/06 Ricardo Silveira 15
 M= (Σ, Q, δ, q0,F)
∑ alfabeto de símbolos de entrada; 
Q conjunto de estados possíveis do autômato, o qual é finito;
δ programa ou função de transição: δ: Q x ∑ → 2Q
q0 estado inicial, tal que q0 é elemento de Q
 F conjunto de estados finais, tal que F está contido em Q;
p
p1
a
estado anterior
Conjunto de novos
estados
símbolo lido
p2 pn
aa
Autômato Finito Não-Determinístico
06/09/06 Ricardo Silveira 16
 δ a b
q0 {q0,q1} {q0, q2}
q1 {qf} -
q2 - {qf}
qf {qf} {qf}
q0
q2q1
qf
a b
b
a,b
a
δ1 é representada na tabela
Exemplo de AFND
– Considere a linguagem:L1={w | w possui aa ou bb 
como subpalavra}
● AF: M1=({a,b},{q0,q1,q2,qf}, δ
2
, q0, {qf})
a,b
06/09/06 Ricardo Silveira 17
Exemplo de AFND
06/09/06 Ricardo Silveira 18
Equivalência entre AFD e AFND
● A partir de um AFND é possível construir um AFD
06/09/06 Ricardo Silveira 19
Determinismo X Não-determinismo
● Muitas vezes é mais fácil desenvolver um 
AFN do que um AFD
– exemplo
● { w | o quinto símbolo da direita para a esquerda de w 
é a }
● solução determinista: não é trivial; número grande de 
estados
● solução não-determinista: bem simples, poucos 
estados
● Alternativa para construir um AFD
– desenvolver inicialmente AFN
06/09/06 Ricardo Silveira 20
Exemplo
● M6 = ({ a, b }, { q0, q1, q2, qf }, δ6, q0, { qf })
06/09/06 Ricardo Silveira 21
Exemplo
● Tabela de transição de estados do AFD
06/09/06 Ricardo Silveira 22
Exemplo
● Grafo do AFD resultante do AFN
06/09/06 Ricardo Silveira 23
Exemplo
● Dado o AFND M = ({q0, q1}, {0, 1}, δ, q0, {q1}) e
– δ(q0, 0) = {q0, q1} 
– δ(q0; 1) = {q1}
– δ(q0; 1) = φ; 
– δ(q1; 1) = {q0, q1} 
● Construir o AFD M0 equivalente.
06/09/06 Ricardo Silveira 24
Exemplo
● Tabela do AFND Tabela do AFD
06/09/06 Ricardo Silveira 25
 M= (Σ, Q, δ, q0,F)
∑ alfabeto de símbolos de entrada; 
Q conjunto de estados possíveis do autômato, o qual é finito;
δ programa ou função de transição: δ: Q x (∑ U {ε}) → 2Q
q0 estado inicial, tal que q0 é elemento de Q
 F conjunto de estados finais, tal que F está contido em Q;
p
p1
a
estado anterior
Conjunto de novos
estados
símbolo lido
p2 pn
aε
Autômato Finito com 
Movimentos Vazios AFε
06/09/06 Ricardo Silveira 26
Diagrama de um AFε 
06/09/06 Ricardo Silveira 27
Exemplo
06/09/06 Ricardo Silveira 28
Exemplo
q
0
q
1
q
2
q
3
q
5
q
4
0,1, ..., 9
0,1, ..., 9 0,1, ..., 9
0,1, ..., 9
.● Um AFε que aceita numeros decimais compostos 
por um sinal opcional (+ ou -) e digitos separados 
por um ponto decimal
ε,+,- .
06/09/06 Ricardo Silveira 29
Computação vazia
06/09/06 Ricardo Silveira 30
Exemplo
06/09/06 Ricardo Silveira 31
Computaçao nos AFε
06/09/06 Ricardo Silveira 32
Computaçao nos AFε
● Função Programa Estendida (computação)
– M= (Σ, Q, δ, q0,F)
06/09/06 Ricardo Silveira 33
Exemplo
06/09/06 Ricardo Silveira 34
Exemplo
06/09/06 Ricardo Silveira 35
Equivalência entre AFN e AFε
● construção de uma função programa sem movimentos 
vazios
● conjunto de estados destino de cada transição não-
vazia
– ampliado com os demais estados possíveis de serem 
atingidos exclusivamente por transições vazias
06/09/06 Ricardo Silveira 36
Equivalência entre AFN e AFε
06/09/06 Ricardo Silveira 3730
Expressões Regulares X Linguagens 
Regulares
● Se r é uma expressão regular ela foi gerada por uma 
LR;
● Uma linguagem é regular, se e somente se, é 
possível construir um AF (AFD, AFND, AFε ) que 
reconheça a linguagem.
● Portanto, para determinar que uma expressão é 
regular deve-se construir um AF a partir dela.
06/09/06 Ricardo Silveira 3830
Expressões Regulares X Linguagens 
Regulares
06/09/06 Ricardo Silveira 3930
Expressões Regulares X Linguagens 
Regulares
06/09/06 Ricardo Silveira 4030
Expressões Regulares X Linguagens 
Regulares
06/09/06 Ricardo Silveira 4130
Expressões Regulares X Linguagens 
Regulares
06/09/06 Ricardo Silveira 4230
Expressões Regulares X Linguagens 
Regulares
06/09/06 Ricardo Silveira 43
Exemplo
06/09/06 Ricardo Silveira 44
Exemplo
06/09/06 Ricardo Silveira 45
Exemplo
06/09/06 Ricardo Silveira 46
Gramática Regular → 
Linguagem Regular
06/09/06 Ricardo Silveira 47
Gramática Regular → 
Linguagem Regular
06/09/06 Ricardo Silveira 48
Construção de um AFε a partir 
de uma GR
06/09/06 Ricardo Silveira 49
Construção de um AFε a partir 
de uma GR
06/09/06 Ricardo Silveira 50
Linguagem Regular → 
GramáticaRegular
06/09/06 Ricardo Silveira 51
Linguagem Regular → 
GramáticaRegular
06/09/06 Ricardo Silveira 52
Construção de uma GR a partir 
de um AFε
06/09/06 Ricardo Silveira 53
Construção de uma GR a partir 
de um AFε