2
Sumário
FACIN-PPGCC
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
Teoria da Computabilidade
Parte I - Teoria de Autômatos
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
Ney Laert Vilar Calazans & Avelino Zorzo
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
{calazans,
calazans, zorzo
zorzo}@
}@inf.pucrs.br
inf.pucrs.br
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
Última atualização – 03/09/2009
3
11. DECIDIBILIDADE
4
1. Pano de Fundo
• A teoria por trás de computadores
– Modelos matemáticos para descrever:
• partes do computador
• tipos de computadores
• máquinas similares (e.g. sistemas embarcados)
• Modelos matemáticos:
–
–
–
–
Abstraem
Simplificam
Codificam
Assim, permitem racionalizar e descobrir sobre o
que se modela
1. Pano de Fundo
• Matemático?
– Modelos, por raciocínio dedutivo conclusões
– Noção de prova - fundamental
• Conclusões em Teoria da Computabilidade
– O que pode ou não pode ser feito!
• Computadores - não mencionados
• Usa-se modelos matemáticos - Máquinas!
• (Coleção de) Entradas de uma máquina
– Linguagem
• antes não era claro!
1
5
6
1. Pano de Fundo
1. Pano de Fundo
• Fundamentos da Teoria da Computabilidade
• Lógica matemática
• Necessidade de Hilbert
– Codificar linguagem universal na qual expressar
• algoritmos
• procedimentos
• programas
– Teoria de conjuntos, Georg Cantor e conjuntos
infinitos
– 1900 - Hilbert e seus problemas - 23 áreas
– Um dos 23 problemas - teoria de conjuntos
– Todo resultado comprovável é verdadeiro ou
– Todo resultado verdadeiro é comprovável?
– Hilbert desejava - método geral de prova!
– Hilbert revisitado no século XXI:
• 1931 - Kurt Gödel:
– Não existe algoritmo para prover provas para
todas as asserções verdadeiras em matemática!
• Conseqüência:
– 1 - Que asserções têm provas? (Computabilidade)
– 2 - Como se pode gerar estas provas? (Algoritmo)
• conjunto de programas de computador para resolver
(quaisquer) problemas matemáticos
7
Sinônimos
8
1. Pano de Fundo
• Resultados (Church, Kleene, Post, Markov,
von Neumann e Turing):
– Blocos construtivos (poucos e simples) de
modelo universal para algoritmos
– Máquina algorítmica universal
• Turing mostrou:
– Certas questões sobre a máquina a máquina não
é capaz de responder!
• Conseqüências:
1. Pano de Fundo
• Em paralelo:
– Invenção da válvula eletrônica
– Segunda Guerra Mundial
• Vastas somas em dinheiro
• Problema prático - quebrar o código da Enigma (Turing)
• Começo
– Um teorema sobre teoremas
• Hoje
– A invenção mais usada desde a roda!
– Fim da esperança de Hilbert (definitivamente)
– Modelo de Turing pode ser construído!
2
9
10
1. Pano de Fundo
1. Pano de Fundo
• Além da lógica matemática
• Áreas fundamentais de teoria da
computabilidade
– Linguística formal
•
•
•
•
O que é linguagem?
Como as pessoas as entendem?
Como as crianças as aprendem?
Chomsky - modelos matemáticos para a descrição de
linguagens
– Teoria de Autômatos - ênfase aqui
– Teoria de Linguagens Formais
– Teoria de Máquinas de Turing - ênfase aqui
– Pensamento e aprendizado - Psicologia e
Neurologia
• McCulloch and Pitts - modelo de rede neural similar a
Turing
11
12
Sumário
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
2. Linguagens
• Elementos definitórios de linguagens formais
–
–
–
–
–
–
Alfabeto - conjunto finito de símbolos
Palavra - seqüência finita de elementos do alfabeto
Regras para a formação de palavras
Sentença - seqüência finita de palavras
Regras para a formação de sentenças
Linguagem - conjunto de sentenças (ou de palavras)
• Linguagens Formais
– onde forma interessa, mais que o significado
• sintaxe interessa, não semântica
– “Eu comi três terça-feiras” sentença correta!
– conceitos de palavra vazia (Λ
Λ) e linguagem vazia (Ø)
3
13
14
2. Linguagens
2. Linguagens
• Definindo Linguagens (Formais)
• Linguagens Formais
– Regras de verificação
– Regras construtivas
– Conjunto de palavras linguagem sobre o alfabeto
de letras (conjunto finito)
– Conjunto de sentenças linguagem sobre o
alfabeto de palavras (conjunto infinito)
•
•
•
•
• Exemplo
–
–
–
–
–
eu comi uma maçã
eu comi duas maçãs
eu comi três maçãs
etc.
– associando gramática definição finita de
linguagem infinita
15
alfabeto Σ = {x}
Linguagem L1 = {x, xx, xxx, xxxx, ]} ou
Linguagem L1 = {xn para n=1, 2, 3, ]}
segunda forma conceito de concatenação
outro conceito comprimento de palavra,
length(w)
• length(xxxx) = 4
• length (Λ
Λ) = 0.
• Se length(w)=0, então w= Λ
16
2. Linguagens
• Exemplo: linguagem Inteiros (p. 11)
• Função reverse
– reverse(xxx) = xxx
– reverse(145) = 541
• Exemplo: linguagem PALINDROME
– Σ = {a, b}
– PALINDROME = {Λ
Λ, e todas as palavras sobre Σ tal
que reverse(x)=x}
• Fechamento de Kleene
– Dado um alfabeto Σ, a linguagem na qual qualquer
palavra (ou cadeia) sobre símbolos do alfabeto
pertence a esta. Simbologia: Σ*
2. Linguagens
• Fechamento de Kleene ou Kleene star
– uma operação
• Ordem lexicográfica
– Σ* = {Λ
Λ 0 1 00 01 10 11 000 001 ...}
• Kleene star de conjunto de palavras
– S - conjunto de palavras
– S* - conjunto de todas as cadeias finitas formadas
pela concatenação de palavras de S
– ATENÇÃO - não confundir ENGLISH-WORDS* com
ENGLISH-SENTENCES
• Exemplos - S={aa b} e T={a ab}. S*, T*?
– Fatoração de palavras e fatoração única
4
17
18
2. Linguagens
2. Linguagens
• Prova por algoritmo construtivo
• Exemplo:
– Exemplo: S={xx xxx}. S* contém todas as cadeias
de x exceto a cadeia x em si. Provar!
– S={a b ab} e T={a b bb}
– S*=T*, porquê?
• x2 e x3 trivialmente existem em S*
• concatenando sucessivos x2 pode-se formar todas as
cadeias de comprimento par
• concatenando sucessivos x2 a x3 pode-se formar todas as
cadeias de comprimento ímpar
• Para excluir a palavra vazia do fechamento,
tem-se:
– se Σ={x}, então Σ+={x xx xxx ]} fechamento positivo
• Exemplo:
• Método de prova mais importante aqui!
• Se Σ=Ø, então Σ*={Λ
Λ}
• Se S={Λ
Λ}, então S*={Λ
Λ}, porque ΛΛ=Λ
ΛΛ Λ
– S={w1 w2 w3}
– S+={w1 w2 w3 w1w1 w1w2 w1w3 w2w1 w2w2 ...}
– Se w1=aa, w2=bbb, w3=Λ
Λ, então S+={aa bbb Λ aaaa
aabbb ]}
– Exceto nos dois casos acima, Kleene star é sempre
conjunto infinito!
19
20
Sumário
2. Linguagens
• Fechamento Kleene de um fechamento Kleene:
– S** ou (S*)*
– Teorema
• Para qualquer conjunto S de cadeias, S*=S**
– Prova
1) Palavra em S**: formada por fatores de S*
2) Fator de S*: formado por fatores de S
3) Palavra em S** é formada por fatores de S
4) palavra de S** é palavra de S*: S** ⊆ S* (Parte 1)
5) S ⊆ S*, pois se pode escolher como palavra qualquer
fator de S.
• 6) S*⊆
⊆ S** por raciocínio análogo (Parte 2)
• 7) juntando as duas relações, tem-se S*=S**
Q.E.D.
•
•
•
•
•
• Problemas: 3/7/11/17/19
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
5
21
22
3. Definições Recursivas
3. Definições Recursivas
• Método para definir conjuntos
• Formado por três passos:
• Exemplo - conjunto dos pares - Definição 2
– R1) 2 é elemento de PARES
– R2) Se x e y são elementos de PARES, x+y é
elemento de PARES
– 1) Especificar alguns dos objetos básicos
– 2) Fornecer regras para construir mais objetos a
partir dos básicos
– 3) Estabelecer que nenhum objeto, exceto os assim
formados fazem parte do conjunto
• Exemplo - conjunto dos inteiros positivos (N*
N*)
– R1) 1 é elemento de INTEIROS
– R2) Se x é elemento de INTEIROS, x+1 é elemento de
INTEIROS
• Exemplo - conjunto dos pares - Definição 1
• Exemplo - conjunto dos inteiros (Z)
– R1) 2 é elemento de PARES
– R2) Se x é par, x+2 é elemento de PARES
– R3) Todos e apenas aqueles elementos obtidos pela
aplicação de R1 e R2 são elementos de PARES
23
– R1) 1 é elemento de INTEIROS
– R2) Se x e y são elementos de INTEIROS, x+y e x-y
são elementos de INTEIROS
24
3. Definições Recursivas
• Exemplo - conjunto dos polinômios
– R1) qualquer número real é elemento de POLINÔMIO
– R2) A variável x é elemento de POLINÔMIO
– R3) Se p e q são elementos de POLINÔMIO, p+q, p-q,
(p) e pq são elementos de POLINÔMIO
• Mais exemplos - (p. 25)
–
–
–
–
–
x+
x*
xodd
INTEIROS
S*
3. Definições Recursivas
• Exemplo importante - expressões aritméticas
– Σ={0 1 2 3 4 5 6 7 8 9 + - * / ( )}
– R1) Qualquer número (positivo/negativo/zero) é
elemento de EA
– R2) Se x é elemento de EA, também o são:
• (x)
• -x, se x não começa com sinal
– R3) Se x e y são elementos de EA, também o são:
•
•
•
•
•
x + y, dado que o primeiro símbolo em y é diferente de + e x - y, dado que o primeiro símbolo em y é diferente de + e x*y
x/y
x**y
6
25
26
Sumário
3. Definições Recursivas
• Teoremas 2/3/4 (EA)
• Fórmulas bem formadas (WFFs)
–
–
–
–
1. PANO DE FUNDO
2. LINGUAGENS
Σ={¬ → ( ) a b c ] y z}
R1) qualquer letra latina é WFF
R2) Se p é WFF, também o são (p) e ¬p
R3) Se p e q são WFFs, também o é p → q
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
• Problemas: 5/7/13/15/16/19
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
27
28
4. Expressões Regulares
•
•
•
•
Novo método para definir linguagens
Mais preciso que uso de elipses (...)
Baseado no conceito de fechamento Kleene
Exemplo:
L4 = {Λ
Λ x xx xxx ...}
O mesmo pode ser dito: dado S={x}, L4=S*
Outra forma L4={x}*
Notação reduzida x* - seqüência de 0 ou mais letras
x x* = Λ ou x ou xx ou xxx ou ]
– L4 = language(x
x*)
–
–
–
–
• Outro exemplo:
– L= {a ab abb abbb abbbb ...} L= language(ab
ab*)
4. Expressões Regulares
• Outros Exemplos:
– L1 = {x xx xxx ...} L1= language(x
x+)
– Language(a
a*b
b*) = {Λ
Λ a b aa ab bb aaa aab abb bbb
aaaa ...}
– Notar que a*b
b* ≠ (ab
ab)*
– L2={xodd} = language(x
x(xx
xx)*) = language ((xx
xx)*x
x)
– Mas L2 ≠ language(x
x*xx
xx*)
• Nova notação: +
– x + y - uma das cadeias x ou y
• Exemplo
– Σ={a b c}, T={a c ab cb abb cbb abbb cbbb ...}
– T=language((a
a + c)b
b*)
7
29
30
4. Expressões Regulares
4. Expressões Regulares
• Para linguagens finitas:
• Definição de Expressão Regular (formal)
– L = {aaa aab aba abb baa bab bba bbb} L=
language((a
a + b)3)
– Símbolos de expressões regulares: letras do
alfabeto Σ, símbolo da palavra vazia Λ, (, ), + e *;
– R1) Toda letra de Σ pode ser uma expressão regular
se escrita em negrito; Λ é uma expressão regular;
– R2) Se r1 e r2 são expressões regulares, também o
são:
• A expressão (a
a + b)* representa todas as
possíveis cadeias do alfabeto {a b}, incluindo a
cadeia vazia
•
•
•
•
(r1
r1)
r1r2
r1 + r2
r1*
r1
– R3) Nada mais é expressão regular.
31
32
4. Expressões Regulares
• Detalhes derivados
– a+ - descartado, pois equivalente a: aa*
– se r1=aa
r1 aa+b
b, r1* é (aa
aa+b
b)*, e não aa+b
aa b*
– linguagem vazia não incluída, formalmente, no
conjunto de expressões regulares, mas aceita-se:
• para toda expressão regular r, r + φ = r e φr = φ
• Exemplos
– (a+b)* a (a+b)*
• conjunto de todas as palavras com pelo menos 1 a
– donde, (a+b)* = (a+b)* a (a+b)* + b*
– mas: a* = a* + a*, a* = a* + a* + a*, a* = a* + aaa
– (a+b)* a (a+b)* a (a+b)* = b* ab* a (a+b)*
4. Expressões Regulares
• Mais exemplos
– b* a b* a b*
• conjunto de todas as palavras com exatamente 2 as
– (a+b)* a (a+b)* b (a+b)* + (a+b)* b (a+b)* a (a+b)*
• conjunto de todas as palavras com pelo menos 1 a e pelo
menos 1 b
• igual a: (a+b)* a (a+b)* b (a+b)* + bb* aa* (Prova na p. 39)
– (a+b)* a (a+b)* b (a+b)* + (a+b)* b (a+b)* a (a+b)* + a*
+ b* = (a+b)* Uma asserção pouco óbvia!!
– Nem toda ER pode ser facilmente expressa em
palavras, e.g.:
• (Λ
Λ + ba*) (ab*a + ba*)* b (a* + b*a) bab*
• Não existe algoritmo para achar o significado de uma ER!
• conjunto de todas as palavras com pelo menos 2 as
8
33
34
4. Expressões Regulares
4. Expressões Regulares
• Mostrando a diferença entre ER e álgebra
–
–
–
–
–
• Definição (multiplicação de conjuntos de
palavras)
(a + b)* = (a + b)* + (a + b)*
(a + b)* = (a + b)* + a*
(a + b)* = (a + b)* (a + b)*
(a + b)* = a (a + b)* + b (a + b)* + Λ
(a + b)* = (a + b)* ab (a + b)* + b*a*
– Se S e T são conjuntos de palavras, define-se o
conjunto produto ST como sendo
• ST = {todas as combinações de uma palavra de S
concatenada com uma palavra de T, nesta ordem}
– Exemplo: S = {a bb bab} e T = {a ab}
• Símbolo * denota (em geral) linguagem infinita
• ST = {aa aab bba bbab baba babab}
– Se L é finita, ER em geral não possui *
• L = {abba baaa bbbb} L = language (abba
abba + baaa + bbbb
bbbb)
• Mais exemplos
– Se V = {Λ
Λ a b ab bb abb bbb abbb bbbb ...},
• V = b* + ab* ou V = (Λ
Λ + a) b* similar à distributividade
algébrica. CUIDADO!!
(ab)* ≠ a*b* !!
35
36
4. Expressões Regulares
• Definição (linguagem associada a uma ER)
– Toda ER define uma linguagem - regras de obtenção:
• R1) linguagem associada com ER que é letra simples é
aquela letra e a linguagem associada a Λ é {Λ
Λ}
• R2) se r1 é ER associada à linguagem L1 e r2 é a ER
associada com a linguagem L2, então:
– (i) a ER (r1
r1) (r2
r2), é associada ao produto de linguagens L1L2
– (ii) a ER r1 + r2 é associada à união de L1 e L2
– (iii) a linguagem associada à ER (r1
r1)* é L1*
– Questões abertas:
• quando ERs diferentes representam a mesma linguagem?
– Algoritmo construtivo do Capítulo 11
4. Expressões Regulares
• Teorema 5 (ERs e linguagens finitas)
– Se L é linguagem finita, L pode ser definida por uma
ER.
– Prova: basta transformar cada palavra em uma ER.
• Dificuldades para entender uma ER (1)
– (a+b)* (aa+bb) (a+b)*
• conjunto de palavras com alguma letra dobrada
– (Λ
Λ+b)(ab)* (Λ
Λ+a)
• conjunto de palavras sem nenhuma letra dobrada
– (a+b)* (aa+bb) (a+b)* + (Λ
Λ+b)(ab)* (Λ
Λ+a) = (a+b)* !!
• toda ER linguagem. Toda linguagem uma ER?
– Não. Discute-se no Capítulo 10
9
37
38
4. Expressões Regulares
4. Expressões Regulares
• Dificuldades para entender uma ER (2)
– E = (a+b)* a (a+b)* (a+Λ
Λ) (a+b)* a (a+b)*
• linguagem associada --> contém pelo menos 2 as
– aplicando distributividade
• E = (a+b)* a (a+b)* a (a+b)* a (a+b)* +
(a+b)* a (a+b)* Λ (a+b)* a (a+b)*
• primeira parte --> qualquer palavra com pelo menos 3 as
• segunda parte --> qualquer palavra com pelo menos 2 as
• ou seja,
“Em resumo, não existe (ou não se conhece) um
conjunto de regras algébricas para reduzir uma
ER a outra equivalente.”
– E= (a+b)* a (a+b)* a (a+b)*
• Outras dificuldades
– (a+b*)* = (a+b)*, mas
– (aa+ab*)* ≠ (aa+ab)*
– (a*b*)* = (a+b)*
39
40
Sumário
4. Expressões Regulares
• Mais um exemplo complicado
– o que produz b*(abb*)* (Λ
Λ + a) ??
• A linguagem de todas as palavras sem 2 as consecutivos!!
• A linguagem EVEN-EVEN
– E = [aa + bb + (ab + ba)(aa + bb)* (ab + ba)]*
• A linguagem que contém todas as palavras com número par
de as e de bs
– A ser usada com freqüência!
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
• Problemas - 5/7/14/17/18
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
10
41
42
5. Autômatos Finitos
5. Autômatos Finitos
• Mais um método para definir linguagens!
• Por quê finito?
• Definição de Autômato Finito - um autômato
finito é uma tripla assim definida:
– Porque o número de estados é finito!
– 1. Um conjunto finito de estados; um estado é o
estado inicial e um subconjunto dos estados
(possivelmente vazio) representam estados finais;
– 2. Um alfabeto Σ de possíveis letras de entrada;
– 3. Um conjunto finito de transições, que designa
qual o estado para onde ir a partir da recepção de
uma letra de entrada, estando o autômato em um
dado estado.
• Por quê autômato?
– Porque a transição entre estados é governada
unicamente pela suas entradas (como autômato, não
tem vontade própria!)
• Em inglês se usa o termo em grego:
– um automaton
– vários automata
43
44
5. Autômatos Finitos
• Definição descreve o que é autômato, não
como ele funciona. Funcionamento:
– a partir do estado inicial, dada um seqüência de
letras de entrada, o autômato transiciona entre
estados, uma para cada letra processada na
seqüência dada.
• Exemplo de autômato finito (FA)
– 1. S={x, y, z}; 2. Σ={a,b}; 3. Transições:
•
•
•
•
•
3.1 - de x, com entrada a, vá para y.
Estado inicial
3.2 - de x, com entrada b, vá para z.
Estados finais
3.3 - de y, com entrada a, vá para x.
3.4 - de y, com entrada b, vá para z.
3.5 - de z, com qualquer entrada, permaneça em z.
5. Autômatos Finitos
• Dada uma seqüência de letras (uma palavra)
– autômato aceita palavra se, partindo do estado
inicial, o processamento de toda a seqüência deixa
o autômato em algum estado final.
• Conjunto de palavras aceitas definem a
linguagem aceita pelo autômato
• Autômato aceita ou rejeita palavras
• Autômatos podem ser vistos como
reconhecedores de linguagens
• Exercício - definir uma ER para a linguagem
aceita para o autômato exemplo! (aa+b
b)*b
b (a
a+b
b)*
11
45
46
5. Autômatos Finitos
5. Autômatos Finitos
• Formatos de apresentação de autômatos
• Exemplos
– 1. Aceita (a+b)(a+b)* = (a+b)+
– tabelas de transição - para o exemplo, tem-se:
a
y
x
z
x (Inicial)
y
z (Final)
-
a
y
a
b
b
b
a, b
+/-
– 3. Não aceita nada (nem Λ), porquê?
Testar funcionamento
para as palavras:
a
a, b
- aaabba
b
- bbaabbbb
z+
a
+
– 2. Aceita (a+b)*
– diagramas de transição - para o exemplo, tem-se:
x-
a
a, b
b
z
z
z
b
47
48
5. Autômatos Finitos
• FAs e as linguagens definidas por eles
– Quando se define linguagens com ER
• Fácil gerar palavras aceitas pela linguagem
• Difícil avaliar se dada palavra é aceita
5. Autômatos Finitos
• Exemplos
– Linguagem sobre Σ={a,b} que aceita palavras com
número de letras par
a,b
– Oposto ocorre com FAs
• Fácil avaliar se palavra pertence à linguagem
• Menos fácil definir subconjunto de palavras aceitas
– Assim questões importantes sobre máquinas
(ER/FA):
• Dada uma linguagem, pode-se construir uma máquina?
• Dada uma máquina, pode-se deduzir sua linguagem?
1-+
2
a,b
– Linguagem dada por a(a
a+b
b)*
b
x-
y
a
z+
b
xa,b
Ou
a,b
a
z+
a,b
y
a,b
t+
a,b
12
49
50
5. Autômatos Finitos
5. Autômatos Finitos
• Exemplo: Construir linguagem sobre Σ={a,b}
que aceita palavras com triplos as ou triplos bs
– 1.
a
a
-
a
• Exemplo: Que linguagem é aceita pelo FA?
a
+
a
a
– 2.
a
-
a
-
b
+
b
a
b
b
a,b
b
– A linguagem (a+b)*(aa+bb) (a+b)*
a
-
+
a
b
b
– 3.
b
b
a
a
+
a
b
b
a,b
51
52
5. Autômatos Finitos
• Mais exemplos (páginas 64-71):
–
–
–
–
–
–
–
–
(a+b)(a+b)b(a+b)*
baa
baa + ab
linguagem que aceita qualquer cadeia de as e bs
onde o número de bs é múltiplo de 3 (com e sem Λ)
linguagem {Λ
Λ}
(a+b)*a
linguagem de todas as palavras que não terminam
com b
linguagem de todas as palavras que possuem
número ímpar de as
5. Autômatos Finitos
• Mais exemplos (páginas 68/69/70/71):
– linguagem de todas as palavras que possuem dois
as consecutivos
– linguagem de todas as palavras onde a primeira
letra é diferente da última
– EVEN-EVEN
– FA para detectar a subcadeia “cat” em um texto em
inglês, composto de letras e espaços
• Problemas:
2/3/4/6/7/16/17/19
13
53
54
Sumário
6. Grafos de Transição
• Mais um método para definir linguagens!
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
• Muito parecido com FAs, mas mais flexível
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
• Mais propenso a confusões de interpretação
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
55
56
6. Grafos de Transição
6. Grafos de Transição
• Relaxando as restrições sobre FAs:
– 1. Múltiplas letras por transição
ba
-
+
b
a,b
aa,ab,bb
– 2. Transições implícitas
-
baa
a,b
Tudo mais
a,b
+
• Definição de aceitação de uma palavra por um
grafo de transição
a
– Em um grafo de transição, quando uma palavra que
não foi completamente processada alcança um
estado que ela não pode deixar porque não existe
aresta de saída que possa ser seguida, diz-se que a
máquina (ou a entrada) quebra (em inglês,
“crashes”) naquele estado. Execução então termina
e a entrada é rejeitada.
Eqüivale a:
a,b
-
baa
+
14
57
58
6. Grafos de Transição
6. Grafos de Transição
• Definição de Grafo de Transição (TG)
• Problemas com grafos de transição (TG)
– o TG abaixo aceita ou não a cadeia baa?
a,b
– Um grafo de transição é uma tripla assim definida:
– 1. Um conjunto finito de estados; pelo menos um
estado é o estado inicial (-) e um subconjunto dos
estados (possivelmente vazio) representam estados
finais (+);
– 2. Um alfabeto Σ de possíveis letras de entrada, a
partir do qual se formam seqüências (“cadeias”);
– 3. Um conjunto finito de transições (rótulos de
arestas do grafo), que designa qual o estado para
onde ir a partir da recepção de uma subseqüência de
letras (inclusive a seqüência vazia Λ), estando o
autômato em um dado estado.
a, b
-
aa,bb
+
– Quantos caminhos distintos de aceitação de
baab existem no TG abaixo?
ab
ba
-
+
baa
b
59
60
6. Grafos de Transição
• IMPORTANTE - o conceito de aceitação de
palavras muda de FA para TG:
– Em FAs toda palavra é aceita ou rejeitada de forma
determinística (todos os caminhos são
explicitamente definidos, toda transição depende de
processar exatamente uma letra do alfabeto)
– Em TGs uma palavra é aceita se existe pelo menos
uma maneira de processar toda a palavra de forma a
chegar em algum estado final. Se a mesma palavra
levar a quebras (crashes) ou estados não finais,
estes caminhos são ignorados (dado que a primeira
condição seja atendida).
6. Grafos de Transição
• Exemplos (páginas 80-85):
TGs com transições associadas à Λ
baa
TGs com vários estados iniciais (simulados ou não)
exemplos de TGs com L={}, L={Λ
Λ}
(a
a+b
b)*b
b
a(a
a+b
b)*b
b + b(a
a+b
b)*a
a
TG que aceita palavras terminadas por pelo menos 3
bs consecutivos e que tem as sempre aos pares
– TG para EVEN-EVEN
– TG que aceita aa de infinitas maneiras
–
–
–
–
–
–
–
• Sempre há como eliminar arestas Λ (Chap 7)
15
61
62
6. Grafos de Transição
6. Grafos de Transição
• Definição - Grafo de Transição Generalizado
(GTG)
• Não-determinismo
– a seguinte construção é possível (se não fosse,
seria facilmente reproduzível de outras formas
menos claras):
– Um grafo de transição é uma tripla assim definida:
– 1. Um conjunto finito de estados; pelo menos um
estado é estado inicial (-) e um subconjunto dos
estados (possivelmente vazio) são estados finais (+);
– 2. Um alfabeto Σ de possíveis letras de entrada;
– 3. Um conjunto finito de arestas conecta alguns
pares de estados, cada uma destas sendo rotulado
com uma expressão regular.
a*
-
(ab+a)*
(b+Λ
Λ)
63
3
...
abb
4
...
abb
5
...
– o caminho para aceitar uma cadeia em um TG NÃO
depende apenas das entradas, a máquina propicia
algumas determinações por si!!
a*
64
Sumário
6. Grafos de Transição
• Problemas:
1/2/3/6/8/15/19
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
16
65
66
7. Teorema de Kleene
7. Teorema de Kleene
• Teorema 6 (Teorema de Kleene - 1956)
• Estrutura da Prova:
– Qualquer linguagem que pode ser definida por:
– Parte 1 - Toda linguagem que pode ser definida por
um autômato finito também pode ser definida por
um grafo de transição.
– Parte 2 - Toda linguagem que pode ser definida por
um grafo de transição também pode ser definida por
uma expressão regular.
– Parte 3 - Toda linguagem que pode ser definida por
uma expressão regular também pode ser definida
por um autômato finito.
• uma expressão regular, ou
• um autômato finito, ou
• um grafo de transição
pode ser definida por qualquer dos três métodos.
• Resultado mais fundamental e mais importante
da teoria de autômatos finitos
• Lógica da prova - razoavelmente complexa
– para provar equivalência de três asserções
ZAPS=ZEPS=ZIPS, prova-se que:
• ZAPS ⊂ ZEPS ⊂ ZIPS ⊂ ZAPS
67
68
7. Teorema de Kleene
• Prova da Parte 1 (Toda linguagem que pode ser definida por um
autômato finito também pode ser definida por um grafo de transição)
– Parte mais fácil (decorre das definições de FA e TG)
• Todo FA é um TG. Logo, toda L definida por um FA já está
automaticamente definida por um TG.
• Prova da Parte 2 (Toda linguagem que pode ser definida por um
grafo de transição também pode ser definida por uma expressão regular)
– Algoritmo construtivo para para transformar um TG
em uma expressão regular
– Para ser válido como prova todo algoritmo deve:
7. Teorema de Kleene
• Primeiros passos do algoritmo (Parte 2). Sem
alterar linguagem aceita:
– Transformar TG para ter apenas 1 estado inicial
– Fazer estado inicial não ter nenhuma aresta
entrando nele
– Transformar TG para ter apenas 1 estado final
– Fazer estado final não ter nenhuma aresta saindo
dele
• valer para qualquer TG
• terminar em tempo finito (executar em número finito de
passos)
17
69
70
7. Teorema de Kleene
b
1-
ab
• Segundo passo do algoritmo (Parte 2). Itera
com terceiro passo. Sem alterar linguagem
aceita:
b
...
2
7. Teorema de Kleene
9+
aa
3-
aa
5-
4
...
...
aba
Torna-se:
Λ
-
Λ
Λ
– Eliminar arestas paralelas, ou seja, as que têm
mesma origem e mesmo destino
12+
b
Torna-se:
r2
...
1
b
2
ab
...
4
...
⇒
...
aba
+
Λ
...
...
⇒
...
x
...
r3
r1
Λ
aa
...
aa
5
x
b
9
3
r1+r2+r3
r1
3
7
...
3
r1+r2
7
...
r2
12
b
71
72
7. Teorema de Kleene
7. Teorema de Kleene
• Terceiro passo do algoritmo (Parte 2). Itera com
segundo passo. Sem alterar linguagem aceita:
• Terceiro passo (continuação)
r3
– Eliminar todos os vértices diferentes de – e +
...
...
...
1
1
r1
2
r1
2
r2
r3
r3
3
3
...
...
⇒
⇒
...
...
1
1
r1r3
r1r2*r3
3
...
1
r1
2
r4
3
...
4
...
5
...
⇒
r2
r5
⇓
r1r2*r3
3
...
...
1
r1r2*r4
3
...
4
...
5
...
r1r2*r5
18
73
74
7. Teorema de Kleene
7. Teorema de Kleene
• Algoritmo construtivo (prova da Parte 2):
• Prova da Parte 3 (Toda linguagem que pode ser definida por
uma expressão regular também pode ser definida por um autômato finito)
– Passo 1 – Criar um único estado – inentrável, e um
único + insaível
– Passo 2 – Um a um, elimine estados diferentes de –
e + no TG, alterando o mesmo para manter a
linguagem intacta, segundo as regras anteriores
– Passo 3 – Quando dois estados são unidos por mais
de uma aresta na mesma direção, unifique-as,
somando seus rótulos
– Passo 4 – Quando tudo que sobrar for – e + e uma
aresta os unindo, a expressão regular sobre esta
aresta gera a mesma linguagem que o TG de partida.
75
– A mais complicada
– Série de algoritmos construtivos para converter ERs
em FAs
– Um algoritmo para cada elemento definitório de
ERs:
•
•
•
•
letras e a palavra vazia (Regra 1)
alternativa (+) (Regra 2)
concatenação (Regra 3)
fechamento Kleene (*) (Regra 4)
– Cada Regra - prova correspondente
76
7. Teorema de Kleene
7. Teorema de Kleene
• Regra 1 – Existe um FA que aceita qualquer
letra do alfabeto e existe um FA que aceita
somente a palavra vazia (Λ
Λ).
• Prova:
– 1) se x está em Σ, então o FA abaixo aceita apenas a
palavra x.
Qquer letra
Qquer letra exceto x
-
x
+
...
Qquer letra
– 2) um FA que aceita apenas Λ aparece abaixo.
Qquer letra
-/+
Qquer letra
• Regra 2 – Se existe FA1 que aceita L1=L(r1) e
FA2 que aceita L2=L(r2), existe FA3 que aceita
L3=L(r1+r2), onde r1 e r2 são ERs.
• Prova (algoritmo construtivo no livro)
– Como construir FA3 de FA1 e FA2? Exemplos
– Guia para a solução – estados de FA3 registram
onde se encontram FA1 e FA2 a cada letra
processada
– Se FA1 tem n estados e FA2 tem m estados FA3 terá
no máximo n.m estados
– Cada estado de FA3 corresponde a um par de
estados, um de FA1 e um de FA2.
19
77
78
7. Teorema de Kleene
7. Teorema de Kleene
• Regra 3 - Se existe FA1 que aceita L1=L(r1) e
FA2 que aceita L2=L(r2), existe FA3 que aceita
L3=L(r1r2), onde r1 e r2 são ERs.
• Prova – Algoritmo Construtivo
• Regra 4 - Se existe FA1 que aceita L1=L(r1),
existe FA2 que aceita L2=L(r1*), onde r1 é ER.
• Prova – Dado um FA1 com estados x1,x2,...
– 1) Criar um estado para cada subconjunto de
“xizes”. Eliminar subconjuntos que contenham um
estado final e não contenham o estado inicial.
– 2) Para todos os estados não-vazios, desenhar uma
aresta ‘a’ e uma aresta ‘b’ para toda coleção de
estados alcançável no FA original a partir dos
“xizes” componentes do estado de partida, via uma
única aresta ‘a’ ou ‘b’, respectivamente.
• 1 – Criar um estado z para cada estado x não-final de FA1,
alcançado antes de alcançar qualquer estado final de FA1.
• 2 – Para cada estado final de FA1, estabelecer um estado z
que expressa as opções de continuar em FA1 ou ir para FA2.
• 3 – Após alcançar um estado salta-para-FA2 qualquer estado
alcançado possui possibilidades x e y como na máquina
união, com a opção adicional de que toda vez que se
alcança um estado final de FA1 pode-se de novo exercitar a
opção de ir para y1 (primeiro estado de FA2)
• 4 – Os estados finais são os estados z que “contêm” algum
estado final de FA2.
79
80
7. Teorema de Kleene
• Prova – Continuação
– 3) Nomear o estado vazio com -/+ e o conectar a
quaisquer estados que o estado de partida esteja
conectado por arestas ‘a’ ou ‘b’, mesmo o próprio
estado inicial.
– 4) Colocar sinais + em todo estado contendo um
componente x que é estado final no FA1
7. Teorema de Kleene
• Definição de Autômato Finito Nãodeterminístico:
– É um TG com um único estado inicial e com a
propriedade que cada um dos rótulos de suas
arestas é uma única letra do alfabeto.
• Teorema 7
– Para todo NFA, existe um FA que aceita a mesma
linguagem.
• NFAs e o Teorema de Kleene
– NFAs e o Teorema 7 fornecem outro meio de realizar
a prova do Teorema de Kleene
• Problemas:
1/2/4/5/6/14
20
81
82
Sumário
8. Autômatos Finitos com Saída
• Em busca de um modelo (matemático) de um
computador
• cadeia de Entrada – programa(s) e dados
• Ler letras de um FA ≡ executar instruções,
escrever na memória externa, etc.
• Parte do etc. são as saídas!
• Saída pode ser vista como parte do estado
• Ou não! Única tarefa que máquinas realizam
até agora é reconhecer uma linguagem
• Se geração de saídas for explicitada, isto
muda!
1. PANO DE FUNDO
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
83
84
8. Autômatos Finitos com Saída
• Definição de Máquinas de Moore (1956) – É
uma quíntupla formada por:
– 1. Um conjunto finito de estados q0, q1, q2,..., onde
q0 é o estado inicial;
– 2. Um alfabeto Σ de possíveis letras de entrada;
– 3. Um alfabeto Γ de caracteres de saída;
– 4. Uma tabela de transição, que designa para cada
par (estado, letra de entrada) qual o estado para
onde ir a seguir;
– 5. Uma tabela de saída, que designa para cada
estado qual o caractere de saída a ser impresso.
8. Autômatos Finitos com Saída
• Definição de Máquinas de Mealy (1955) – É uma
quádrupla formada por:
– 1. Um conjunto finito de estados q0, q1, q2,..., onde
q0 é o estado inicial;
– 2. Um alfabeto Σ de possíveis letras de entrada;
– 3. Um alfabeto Γ de caracteres de saída;
– 4. Uma representação pictórica, na forma de um
grafo onde vértices representam estados e arestas
representam transições entre estados. Arestas são
dotadas de rótulos x/y, representando a letra de
entrada que produz a transição (x) e a letra de saída
gerada pela transição (y).
21
85
86
8. Autômatos Finitos com Saída
8. Autômatos Finitos com Saída
• Lembrando
• Moore = Mealy
– Máquinas de Moore/Mealy não aceitam/rejeitam
cadeias (ação não definida)
– Saída pode funcionar para identificar tal
reconhecimento
– Por exemplo, uma máquina pode escrever 1 para
indicar reconhecimento de palavra de uma
linguagem e escrever 0 caso contrário.
– Definição de equivalência – dada uma máquina de
Mealy Me e uma máquina de Moore Mo, que imprime
o caractere x no estado inicial, diz-se que Me e Mo
são equivalentes se para qualquer cadeia de entrada
a cadeia de saída de Mo é exatamente x
concatenado com a cadeia de saída de Me.
– Teorema 8
• Se Mo é uma máquina de Moore, então existe uma máquina
de Mealy Me que é equivalente a Mo.
– Teorema 9
• Para toda máquina de Mealy Me, existe uma máquina de
Moore Mo equivalente a Me.
87
88
8. Autômatos Finitos com Saída
8. Autômatos Finitos com Saída
• Prova do Teorema 8 (algoritmo construtivo)
a/t
a
b
c
⇒
q4/t
b/t
c/t
q4
• Prova do Teorema 9 (algoritmo construtivo)
a/0
• Conceito de transdutores
a/1
q2_4/1
b/0
b
a/1
b/1
⇒
q4
b/1
b/1
a
b
a/1
– Autômatos com saídas são ditos transdutores clara conexão com circuitos eletrônicos
– Em transdutores, o número total de estados limita a
quantidade de “história passada” sobre a qual o
circuito se baseia para gerar as suas saídas.
– Estados – vinculados a valores armazenados em
bits de memória de um “registrador de estado”
– e. g. um microprocessador com 3000 bits em seu
registrador de estados pode lembrar-se (no máximo)
do que aconteceu há 23000 ciclos de relógio atrás!
• Problemas:
1/2/3/4/6
q1_4/0
b/1
22
89
90
Sumário
9. Linguagens Regulares
1. PANO DE FUNDO
• Definição de Linguagem Regular: toda
linguagem que pode ser definida por uma
expressão regular.
• Teorema 10
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
– Se L1 e L2 são linguagens regulares, então L1+L2,
L1L2 e L1* são linguagens regulares.
6. GRAFOS DE TRANSIÇÃO
• Prova
7. TEOREMA DE KLEENE
– Baseada na prova do teorema de Kleene, uma vez
que L1 e L2, sendo regulares, têm expressões
regulares que lhes geram.
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
91
92
9. Linguagens Regulares
• Definição de Complemento de Linguagem
Regular: Se L é uma linguagem regular sobre o
alfabeto Σ, define-se seu complemento, L´ como
sendo a linguagem de todas as cadeias de letras
de Σ que não são palavras de L.
• Teorema 11
– Se L é uma linguagem regular, então L´ também é
uma linguagem regular.
• Prova
9. Linguagens Regulares
• Teorema 12
– Se L1 e L2 são linguagens regulares, então L1 ∩ L2
também é linguagem regular.
• Prova
– Usando-se a Lei de de Morgan, que vale para
quaisquer conjuntos, tem-se:
• L1 ∩ L2 = (L1´ + L2´)´
• Como L1 e L2 são regulares, e seus complementos também,
a interseção de L1 e L2 é uma linguagem regular.
• Problemas:
1/2/3/4/18
– Se L é regular, sabe-se que existe um FA que a aceita.
Construir FA´, onde a única diferença é que o(s)
estado(s) final(is) de FA não são finais em FA´ e viceversa. Este FA aceita L´. Logo, L´ é regular.
23
93
94
Sumário
10. Linguagens Não-Regulares
• Problemas:
1. PANO DE FUNDO
1/2/5/15/16(ii)
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
95
96
Sumário
1. PANO DE FUNDO
11. Decidibilidade
• Problemas:
1/2/3/4/5/9/10/11/12/13
2. LINGUAGENS
3. DEFINIÇÕES RECURSIVAS
4. EXPRESSÕES REGULARES
5. AUTÔMATOS FINITOS
6. GRAFOS DE TRANSIÇÃO
7. TEOREMA DE KLEENE
8. AUTÔMATOS FINITOS COM SAÍDAS
9. LINGUAGENS REGULARES
10. LINGUAGENS NÃO-REGULARES
11. DECIDIBILIDADE
24