Mais Propriedades
de
Linguagens Regulares
1
Já provamos
Linguagens Regulares são fechadas sob:
União
Concatenação
Operação Star
Reverso
2
Ou seja, para linguagens regulares
União
L1  L2
Concatenação
L1L2
Operação Star

L1
Reverso
R
L1
L1 e L2
:
Linguagens
Regulares
3
Vamos provar
Linguagens Regulares são fechadas sob:
Complemento
Interseção
4
Ou seja, para linguagens regulares
Complemento
Interseção
L1 e L2
:
L1
L1  L2
Linguagens
Regulares
5
Complemento
Teorema: Para qq linguagem regular L
o complemento L é regular
Prova:
Tome um DFA que aceita L e faça
• os estados não finais finais
• os estados finais não finais
O DFA resultante aceita L
6
Exemplo:
L  L ( a * b)
a
q0
b
q1
a, b
a, b
q2
L  L(a * a * b(a  b)(a  b)*)
a, b
a
q0
b
q1
a, b
q2
7
Interseção
Teorema: Para linguagens regulares L1 e L2
a interseção L1  L2 é regular
Prova:
Use a Lei de DeMorgan:
L1  L2  L1  L2
8
L1 , L2
regular
L1 , L2
regular
L1  L2
regular
L1  L2
regular
L1  L2
regular
9
Representações Padrão
de
Linguagens Regulares
10
Representações Padrão
de Linguagens Regulares
Linguagens Regulares
DFAs
NFAs
Gramáticas
Regulares
Expressões
Regulares
11
Quando dizemos:
Dada uma
Linguagem Regular
L
Queremos dizer: Linguagem L em uma
representação padrão
12
Questões Elementares
sobre
Linguagens Regulares
13
Questão da Pertinência
Questão: Dada uma linguagem regular L
e um string w
como determinar se w Î L ?
Resposta: Tome um DFA que aceita L
e verifique se w é aceito ou não
14
DFA
w
w L
DFA
w
w L
15
Questão:
Dada uma linguagem regular
como podemos determinar
se L é vazia:
( L  ) ?
Resposta: Tome um DFA que aceita
L
L
Verifique se existe um caminho
do estado inicial até o estado final
16
DFA
L
DFA
L
17
Questão:
Dada um linguagem regular
como podemos determinar
se L é finita?
Resposta: Tome um DFA que aceita
L
L
Verifique se existe um caminho do
estado inicial para um estado final
que possua um ciclo
18
DFA
L é infinita
DFA
L é finita
19
Questão: Dadas linguagens regulares L e
1
como determinar se L1  L2 ?
L2
Resposta: Determine se
( L1  L2 )  ( L1  L2 )  
20
( L1  L2 )  ( L1  L2 )  
e
L1  L2  
L1
L2 L
2
L1  L2
L1  L2  
L2
L1 L1
L2  L1
L1  L2
21
( L1  L2 )  ( L1  L2 )  
L1  L2  
L1
ou
L1  L2  
L2
L2
L1  L2
L1
L2  L1
L1  L2
22
Linguagens Não Regulares
23
Linguagens
Não Regulares
{a b : n  0}
n n
{ww : w {a, b}*}
R
Linguagens Regulares
a *b
b*c  a
b  c ( a  b) *
etc...
24
Como podemos provar que uma linguagem
não é regular?
L
Provar que não existe um DFA que aceite
L
Problema: isso não é fácil de provar
Solução: Lema do Bombeamento !!!
25
Antes de formular o Lema do Bombeamento,
vamos introduzir sua idéia básica por meio
de um exemplo
DFA com
b
q1
4 estados
b
b
a
q2 b
a
q3
b
q4
a
32
Nos caminhos dos strings:
a
aa
aab
b
q1
nenhum estado
é repetido
b
b
a
q2
a
a
q3
b
q4
a
33
Nos caminhos dos strings:
aabb
bbaa
algum estado
é repetido
abbabb
abbbabbabb...
b
q1
b
a
q2
a
a
q3
b
b
q4
a
34
Se o caminho de um string w
tem comprimento | w |  4
então algum estado é repetido
b
q1
b
b
a
q2
a
a
q3
b
q4
a
35
Se em um caminho de um string w
no. de transições  estados do DFA
então algum estado é repetido
b
q1
b
b
a
q2
a
a
q3
b
a
q4
36
Em geral:
String
w tem comprimento  no. de estados
Um estado q deve ser repetido no caminho de w
caminho de
w
......
q
......
38
Lema do Bombeamento
39
Seja L uma linguagem regular infinita
DFA que aceita
L
m
estados
40
Tome um string
w tal que w L
Existe um caminho com rótulo
w:
.........
caminho
w
41
Se o string w tem comprimento | w |
 m
número de estados
então algum estado
q é repetido no caminho w
......
caminho
q
w
......
42
Escreva
w x y z
y
......
x
q
......
z
43
| x y |  m número
Observações:
de estados
| y | 1
y
......
x
q
......
z
44
Observação:
O string
x z é aceito
y
......
x
q
......
z
45
Observação:
O string
é aceito
xyyz
y
......
x
q
......
z
46
Observação:
O string
é aceito
xyyyz
y
......
x
q
......
z
47
Em Geral:
i
O string
é aceito
xy z
i  0, 1, 2, ...
y
......
x
q
......
z
48
Em outras palavras, nós descrevemos:
O Lema do Bombeamento !!!
49
O Lema do Bombeamento:
• Dada uma linguagem regular infinita
• existe um inteiro
m
w L com | w |  m
• para todo string
• podemos escrever
• com
|x y|  m
• tal que:
L
w x y z
e
xy z  L
i
| y | 1
i  0, 1, 2, ...
50
Aplicações
do
Lema do Bombeamento
51
Teorema: A linguagem
L  {a b : n  0}
n n
não é regular
Prova:
Use o Lema do Bombeamento
52
L  {a b : n  0}
n n
Suponha, por contradição,
que L é uma linguagem regular
Como L é infinita
podemos aplicar o Lema do Bombeamento
53
L  {a b : n  0}
n n
Seja
m o inteiro do Lema do Bombeamento
Tome um string
w tal que: w  L
comprimento
Exemplo:
tome
| w| m
wa b
m m
54
Escreva: a
b xyz
m m
Pelo Lema do Bombeamento
deve ser verdade que | x y |  m,
| y | 1
m
Portanto:
m m
a b
m
 a...aa...a...ab...b
x
y  a , k 1
y
z
k
55
x y za b
y  a , k 1
m m
Temos:
Do Lema do Bombeamento:
k
xy z  L
i
i  0, 1, 2, ...
Portanto:
xy z  L
2
xy z  xyyz  a
2
m k m
b
 L
56
Portanto:
MAS:
a
m k m
b L
L  {a b : n  0}
n n
a
m k m
b L
CONTRADIÇÃO!!!
57
Portanto:
Nossa hipótese de que L
é uma linguagem regular
não é verdadeira!
Conclusão: L não é uma linguagem regular
58
Linguagens Não Regulares
{a b : n  0}
n n
Linguagens Regulares
a *b
b*c  a
b  c ( a  b) *
etc...
59