Buscar

Aula 04 de Teoria da Computação (Expressões Regulares e Lema do Bombeamento)

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 21 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 21 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 21 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Roteiro da Aula 4
1 Expresso˜es Regulares
Exemplos e exerc´ıcios
Equivaleˆncia AFN/Expresso˜es Regulares
2 Situac¸a˜o Atual
3 Linguagens na˜o-regulares
Pumping Lemma
4 Discusso˜es
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Operac¸o˜es regulares – Semaˆntica
Seja Σ um alfabeto e L, L1 e L2 linguagens sobre Σ:
• Unia˜o: L1 ∪ L2 = {x | x ∈ L1 ou x ∈ L2};
• Concatenac¸a˜o: L1L2 = {xy | x ∈ L1 e y ∈ L2};
• Se L1 = {00, 01, 10, 11} e L2 = ∅, quem e´ L1L2?
• Por definic¸a˜o: L1 = L, L2 = LL, L3 = LLL, . . . ;
• e L0 = {ε};
• Kleene closure: L∗ =
⋃
∞
i=0
Li.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Exemplos
• L1 = {bad, good} e L2 = {boy, girl}:
• L1L2 = {badgirl, badboy, goodgirl, goodboy};
• Σ = {0, 1}, Σ∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . . };
• ∅∗ = {ε};
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Expresso˜es Regulares
Sa˜o expresso˜es (sequ¨eˆncias de s´ımbolos), definidas recursivamente,
que representam linguagens sobre um alfabeto Σ
Expresso˜es Regulares
Expressa˜o regular representa a linguagem
∅ vazia
ε {ε}
a {a}, para cada a ∈ Σ
(r + s) R ∪ S
(rs) RS
(r∗) R∗
onde r e s sa˜o expresso˜es regulares
representando as linguagens R e S
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Exemplos
Se Σ = {0, 1}:
• (0+ 1)∗;
• ((0(1∗)) + 0);
• abreviando como 01∗ + 0;
• ∗ precede concatenac¸a˜o, que precede +;
• (0+ 1)∗1(0+ 1)(0+ 1);
• rr∗ e´ abreviado como r+;
Usamos L(r) para denotar a linguagem representada pela
expressa˜o regular r.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Exerc´ıcios
Escreva expresso˜es regulares para as seguintes linguagens sobre
{0, 1}:
• as palavras que teˆm exatamente um 1;
• as palavras que teˆm pelo menos um 1;
• as palavras que teˆm tamanho par;
• as palavras que comec¸am e terminam com o mesmo
s´ımbolo;
• as palavras que teˆm um nu´mero par de 0’s e de 1’s.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Equivaleˆncia entre AFN e Exp. Reg.
Teorema
Para toda expressa˜o regular r, existe AFN A, tal que
L(A) = L(r).
Na˜o veremos a rec´ıproca desse teorema, mas...
Linguagem Regular
Uma linguagem L ⊆ Σ∗ e´ Regular se existe uma expressa˜o
regular r tal que L(r) = L.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
0
1
0
1
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
(0 + 1)
1
0
ε
ε
0
1
0
1
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
(0 + 1)
1
0
ε
ε
(0 + 1)∗
0
1
1
0
ε
ε
ε
ε
ε
0
1
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
(0 + 1)
1
0
ε
ε
(0 + 1)∗
0
1
1
0
ε
ε
ε
ε
ε
01 ε
10
0
1
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Exemplos e
exerc´ıcios
Equivaleˆncia
AFN/Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Intuic¸a˜o sobre o Teorema
(0 + 1)
1
0
ε
ε
(0 + 1)∗
1
0
ε
ε
ε
ε
ε
01 ε
ε
ε
ε
0
1
1
0
ε
ε
ε
ε
ε
01 ε
(0 + 1)∗10
10
0
1
(0 + 1)∗10
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Situac¸a˜o Atual
P(Σ∗)
Regulares
Aut. Finito Determin´ıstico
Aut. Finito Na˜o-determin´ıstico
Expresso˜es Regulares
Complementac¸a˜o
Unia˜o
Fechada por:
Intersec¸a˜o
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Situac¸a˜o Atual
P(Σ∗)
Regulares
{0n1n | n ≥ 0}
Aut. Finito Determin´ıstico
Aut. Finito Na˜o-determin´ıstico
Expresso˜es Regulares
Complementac¸a˜o
Unia˜o
Fechada por:
Intersec¸a˜o
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Pumping Lemma
Discusso˜es
O autoˆmato e´ Finito!
L = {w | # de 1’s e # de 0’s e´ par}
1
1
1
1
0 0 0 0
2
34
1
o que acontece se |w| > 4 ?
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Pumping Lemma
Discusso˜es
Pumping Lemma
Pumping Lemma
• Para toda linguagem regular L;
• Existe p ∈ N; tal que
• Para toda palavra w ∈ L, |w| ≥ p;
• Existe x, y, z:
• w = xyz;
• |xy| ≤ p;
• |y| ≥ 1; tal que
• Para todo i ≥ 0, xyiz ∈ L.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Pumping Lemma
Discusso˜es
Pumping Lemma
Pumping Lemma
• Para toda linguagem regular L;
• Existe p ∈ N; tal que
• Para toda palavra w ∈ L, |w| ≥ p;
• Existe x, y, z:
• w = xyz;
• |xy| ≤ p;
• |y| ≥ 1; tal que
• Para todo i ≥ 0, xyiz ∈ L.
Se L e´ regular =⇒ vale o PL para L
↓ contrapositiva
Se na˜o vale o PL para L =⇒ L na˜o e´ regular
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Pumping Lemma
Discusso˜es
Aplicando o PL
Se na˜o vale o PL para L
• Para todo p ∈ N;
• Existe palavra w ∈ L, |w| ≥ p; tal que
• Para todo x, y, z:
• w = xyz;
• |xy| ≤ p;
• |y| ≥ 1;
• Existe i ≥ 0, tal que xyiz 6∈ L.
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Pumping Lemma
Discusso˜es
Aplicando o PL
Se na˜o vale oPL para L
• Para todo p ∈ N;
• Existe palavra w ∈ L, |w| ≥ p; tal que
• Para todo x, y, z:
• w = xyz;
• |xy| ≤ p;
• |y| ≥ 1;
• Existe i ≥ 0, tal que xyiz 6∈ L.
Vamos mostrar que {0n1n | n ≥ 0} na˜o e´ regular...
Teoria da
Computac¸a˜o
116360
Aula 4
Roteiro
Expresso˜es
Regulares
Situac¸a˜o Atual
Linguagens
na˜o-regulares
Discusso˜es
Discusso˜es
A memo´ria e´ finita!
• Em teoria, em princ´ıpio, um PC t´ıpico e´ um AFD;
• Ha´ um nu´mero finito de poss´ıveis estados num PC;
f(n) = 2n na˜o e´, em princ´ıpio, regular!
• Uma formalizac¸a˜o razoa´vel seria semelhante a:
• {0n12n | n ≥ 0};
• que na˜o e´ regular!
e f(n) = n, e´ regular?
	Roteiro
	Expressões Regulares
	Exemplos e exercícios
	Equivalência AFN/Expressões Regulares
	Situação Atual
	Linguagens não-regulares
	Pumping Lemma
	Discussões

Outros materiais