Propriedades das Linguagens Regulares - Parte I

Prévia do material em texto

PROPRIEDADES DAS 
LINGUAGENS REGULARES 
Marcelo Guerra 
INTRODUÇÃO 
 Nem todas as linguagens são regulares 
 
 Estabelecemos que a classe de linguagens conhecidas 
como LR tem pelo menos quatro descrições diferentes 
 DFA 
 NFA 
 ε-NFA 
 ER 
 
 Ferramenta para provar que uma linguagem não é 
regular: lema do bombeamento 
 
 
INTRODUÇÃO 
 Uma propriedade importante sobre as LR é a 
propriedade de fechamento: permite construir 
reconhecedores para linguagens que são construídas 
a partir de outras linguagens por certas operações. 
 Exemplo: a interseção entre duas linguagens regulares 
também é regular 
 Utilidade: construção de autômatos complexos a partir de 
autômatos para reconhecer linguagens mais simples 
 
INTRODUÇÃO 
 Outra propriedade importante sobre LR são as 
Propriedades de decisão: 
 Uma linguagem é reconhecida por um certo autômato? 
 Dois autômatos reconhecem a mesma linguagem 
 
 Aplicações 
 Minimização do número de estados de um autômato – 
encontrar um autômato equivalente, com o mínimo de 
estados possível . 
LEMA DO BOMBEAMENTO 
 Técnica que permite mostrar que certas linguagens 
não são regulares. 
 
 Exemplo de como funciona 
 
 Considere a linguagem L01 = {0
n1n|n ≥1}, que contém 
todos os strings 01,0011,000111 etc. 
 
 Afirmamos que L01 não é regular: se fosse, existiria 
algum AFD A que a reconheceria. 
 
LEMA DO BOMBEAMENTO 
 O lema do bombeamento para linguagens regulares 
determina se uma dada linguagem não é regular. 
 
 Ele não pode ser usado para determinar se a 
linguagem é regular. Embora ele seja verdadeiro 
para todas as LRs. 
 
 Mas, ele é válido para algumas linguagens não 
regulares. 
 
LEMA DO BOMBEAMENTO PARA 
LINGUAGENS REGULARES 
Seja L uma linguagem regular, então: 
 
 Existe uma constante n (que depende de L) tal 
que, para toda string w  L onde |w| ≥ n, 
podemos dividir w em três strings, w = xyz, tais 
que: 
1. y  ε 
2. |xy| ≤ n 
3. Para todo k ≥0, a string xykz  L 
 
 Podemos encontrar uma string não vazia y que 
pode ser “bombeada” ou excluí-la (quando k = 0) 
3.k ≥ 0, xykz ∈ L 
1. |y| ≥ 1 
2. |xy| ≤ n 
PROVA 
 Considere o que se passa quando A recebe uma 
entrada xykz 
 Se k=0, A vai de p0 para pi em x. Em seguida, A vai até o 
estado de aceitação na entrada z 
 Se k > 0, A vai de q0 para pi sobre a entrada x, circula de pi 
para pi k vezes para a entrada y
k e depois vai para o estado 
de aceitação para a entrada z 
 Assim, xykz com k > 0 também é aceito por A 
 
 
p0 pi 
x=a1...ai 
y=ai+1...aj 
z=aj+1...am 
APLICAÇÕES DO LEMA DO BOMBEAMENTO 
 A linguagem Leq que consiste em todos os strings 
com número igual de 0´s e 1´s 
 
 n é a constante que deve existir se Leq for regular. 
 
 Suponha w=0n1n, uma string que pertence a Leq.
 
 
 Desmembramos w em xyz, onde |xy| ≤ n e y  ε, que não 
conhecemos. 
 
APLICAÇÕES DO LEMA DO BOMBEAMENTO 
 Sabendo que |xy| ≤ n , concluímos que xy é prefixo de w, 
consistindo apenas em 0’s. 
 Bombeando a string com k=0, xz possuirá n 1’s, porém existirão 
menos de n 0’s entre x e z, pois perdemos alguns 0’s ao eliminar 
y (e y  e). 
 
 Deste modo, encontramos uma contradição para a regra 
3 do Lema do Bombeamento, o que prova que a 
linguagem não é regular. 
 
3.k ≥ 0, xykz ∈ L 
APLICAÇÕES DO LEMA DO BOMBEAMENTO 
 A linguagem Leq que consiste em todos os strings 
com número igual de 0´s e 1´s 
 
 n é a constante que deve existir se Leq for regular. 
 
 Suponha w=0n1n, uma string que pertence a Leq. 
 Observe que a escolha da cadeia deve ser tal que ela mostre a 
não regularidade da linguagem 
 
 Desmembramos w em xyz, onde para k>=0 a cadeia xykz 
pertence a L se obedecer as seguintes condições. 
 
APLICAÇÕES DO LEMA DO BOMBEAMENTO 
 Se y possui apenas 0s. Nesse caso, xyyz não pertence L. 
Temos uma contradição; 
 
 Se y possui apenas 1s. Nesse caso |xy|  n, violando a 
condição 2. 
 
 Se y possui 0s e 1s, a condição 2 também é violada. Além 
disso, xyyz não pertencerá à linguagem 
 
 Deste modo, encontramos contradições, o que prova que a 
linguagem não é regular. 
 
3.k ≥ 0, xykz ∈ L 
1. |y| ≥ 1 
2. |xy| ≤ n 
TESTE 
 Prove que L={0j10j | j ≥ 1} não é regular. 
 
1. Seja n a constante do lema do bombeamento 
 
2. Escolha w = 0n10n. 
 
3. Então escreva w = xyz. Sabemos que |xy| ≤ n, e portanto 
y consiste em apenas 0's. 
 
4. Assim, xz, que deve estar em L se L for regular, consiste 
em menos que n 0's, seguidos por um 1 e exatamente n 
0's. 
 
5. Tal string não está em L, então contradizemos a hipótese 
de que L é regular. 
LEMA DO BOMBEAMENTO EXEMPLOS 
 
 Mostre que o lema se aplica para L = {bcdncb |n>=0} 
 
3.k≥ 0, xykz ∈ L 
1. |y| ≥ 1 
2. |xy| ≤ n 
b b c c 
d 
n = 5 
w = xyz 
x=bc, y=d e z=cb 
LEMA DO BOMBEAMENTO EXEMPLOS 
 
 Mostre que o lema se aplica para L = {abna| n >=1 
e impar} 
 
n = 4 
s = xyz 
x=ab, y=bb e z=a 
b 
a a 
b 
3.k≥ 0, xykz ∈ L 
1. |y| ≥ 1 
2. |xy| ≤ n 
LEMA DO BOMBEAMENTO EXEMPLOS 
 Seja L= a(bc)*a. Então um AFD para L seria: 
 
 
c b 
a a 
p = 4 
s = xyz 
x=a, y=bc e z=a 
3.k≥ 0, xykz ∈ L 
1. |y| ≥ 1 
2. |xy| ≤ n