Lista 1 3 - Solução

Prévia do material em texto

Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da
Computação 2021/2
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 1 - Parte 3
(Linguagens Não-Regulares)
Leitura necessária:
• Introdução à Teoria da Computação, 2a Edição (Michael Sipser):
– Caṕıtulo 1.4: Linguagens Não-regulares
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) O que diz o lema do bombeamento para linguagens regulares?
Solução do professor: O Lema do bombeamento (LB) para linguagens regulares diz que se
A é uma linguagem regular, então existe um número p (o comprimento de bombeamento) tal
que, se s é qualquer cadeia de A de comprimento no mı́nimo p, então s pode ser dividida em três
subcadeias x, y, z com
s = xyz
satisfazendo as seguintes condições:
1. para cada i ≥ 0, xyiz ∈ A,
2. |y| > 0, e
3. |xy| ≤ p.
(b) Explique como o lema do bombeamento pode ser utilizado para demonstrar que uma linguagem
não é regular.
Solução do professor: Para usar o lema do bombeamento para mostrar que uma linguagem
L não é regular:
1. Assuma que L seja regular.
2. Use o LB para garantir que existe um comprimento p tal que toda palavra s ∈ L com compri-
mento maior que p possa ser bombeada.
3. Encontre uma cadeia s ∈ L com comprimento maior que p que não possa ser bombeada,
mostrando que para qualquer divisão de s = xyz (satisfazendo as condições do LB de que
|y| > 0 e |xy| ≤ p), existe pelo menos um valor de i tal que xyiz /∈ L.
4. Como você chegou a uma contradição, pois (3) contradiz (2), sua hipótese em (1) era falsa, e
L não pode ser uma linguagem regular.
Exerćıcios.
2. (Sipser 1.29 - Itens (a), (c)) Use o Lema do Bombeamento para demonstrar que as seguintes linguagens
não são regulares.
(a) A1 = {0n1n2n | n ≥ 0}
(c) A2 = {a2
n | n ≥ 0} (Aqui, a2n significa uma cadeia formada por 2n a’s.)
1
Solução do professor:
(a) Solução dada no livro-texto.
(c) Solução dada no livro-texto.
3. (Sipser 1.30) Descreva o erro na seguinte “demonstração” de que 0∗1∗ não é uma linguagem regular.
(Um erro deve existir uma vez que 0∗1∗ é regular.) A demonstração é por contradição. Assuma que
0∗1∗ seja regular. Seja p o comprimento de bombeamento para 0∗1∗, dado pelo Lema do Bombeamento.
Escolha s como a cadeia 0p1p. Sabemos que s pertence a 0∗1∗, mas o Exemplo 1.73 mostra que s não
pode ser bombeada. Logo, temos uma contradição, e 0∗1∗ não é regular.
Solução do professor: O Exemplo 1.73 mostra que a linguagem {0n1n | n ≥ 0} não é regular. Para
isto, ele mostra que 0p1p não pode ser bombeada e produzir uma palavra que pertença a {0n1n | n ≥ 0}.
Entretanto, nesta demonstração estamos interessados em mostrar que uma linguagem diferente, 0∗1∗,
não é regular. O erro da demonstração é usar o mesmo procedimento do Exemplo 1.73: ao bombearmos
0p1p produzimos uma palavra fora da linguagem {0n1n | n ≥ 0}, mas, por outro lado, a palavra ainda
pertence à linguagem 0∗1∗ de interesse, e o LB não é contradito. Por isso não podemos concluir que
0∗1∗ não é regular, e a demonstração está errada.
4. (Sipser 1.48) Seja Σ = {0, 1} e seja
D = {w | w contém um número igual de ocorrências das subcadeias 01 e 10}.
Logo 101 ∈ D porque 101 contém uma única ocorrência de 01 e uma única ocorrência de 10, porém
1010 /∈ D porque 1010 contém dois 10’s e apenas um 01. Mostre que D é uma linguagem regular.
Solução do professor: Podemos construir um AFD para a linguagem
D = {w ∈ {0, 1}∗ | w contém um número igual de ocorrências das subcadeias 01 e 10},
como mostra a figura abaixo. Portanto a linguagem D é regular.
5. (Sipser 1.49)
(a) Seja B = {1ky | y ∈ {0, 1}∗ e y contém pelo menos k 1’s, com k ≥ 1 }. Mostre que B é uma
linguagem regular.
(b) Seja C = {1ky | y ∈ {0, 1}∗ e y contém no máximo k 1’s, com k ≥ 1 }. Mostre que C não é uma
linguagem regular.
(c) Se as linguagens regulares são fechadas sob complemento, como é posśıvel que a linguagem B
seja regular, mas a linguagem C não seja?
2
Solução do professor:
a) Para resolver essa questão, vamos primeiro mostrar que a linguagem
B = {1ky | y ∈ {0, 1}∗ e y contém pelo menos k 1s, para k ≥ 1}
é idêntica à linguagem
B′ = {1y | y ∈ {0, 1}∗ e y contém pelo menos um 1}.
Para ver isso, note que B′ ⊆ B (pois apenas fixamos k = 1), e que B ⊆ B′ (pois se w ∈ B, então
evidentemente w ∈ B′).
Agora mostramos que B′ é regular (e, portanto B também é), provendo a seguinte expressão regular
para ela: 1(0 ∪ 1)∗1(0 ∪ 1)∗.
b) Vamos demonstrar por contradição. Assuma que
C = {1ky | y ∈ {0, 1}∗ e y contém no máximo k 1s, para k ≥ 1}
seja uma linguagem regular. Seja p a constante de bombeamento dada pelo lema do bombeamento.
Escolha a palavra s como sendo 1p01p. Como s ∈ C e |s| ≥ p, o LB diz que se pode dividir s em
três partes s = xyz, onde para qualquer i ≥ 0, xyiz ∈ B (que é a primeira condição do LB). A
segunda condição do LB (|xy| ≤ p) nos garante y só pode conter 1’s, uma vez que s começa com p
ocorrências de 1. Além disso, a terceira condição do LB (|y| > 0) garante que y tem ao menos um 1.
Isso quer dizer que y só contém 1s, e que y contém pelo menos um 1. Portanto, a palavra xy0z será
da forma 1p−|y|01p e terá um prefixo com menos 1s do que o sufixo, não pertencendo, portanto, à
linguagem C. Mas isto viola a primeira condição do LB, e chegamos a uma contradição. Portanto
conclúımos que C não é uma linguagem regular.
c) As propriedades de fechamento não são violadas porque as linguagens B e C não são o complemento
uma da outra!
6. Mostre que a linguagem L = {akbmcn | k = m+n} não é regular, usando propriedades de fechamento
de linguagens regulares. (Dica: Use o fato de que já demonstramos que {anbn | n ≥ 0} não é regular.)
Solução do professor: Por contradição. Suponha que L seja uma linguagem regular. Como a∗b∗
é uma linguagem regular (pois existe expressão regular para ela), e a classe das linguagens regulares é
fechada sob interseção, temos que L ∩ a∗b∗ deveria ser também uma linguagem regular.
Porém, note que
{akbmcn | k = m + n} ∩ a∗b∗ = {anbn | n ≥ 0},
o que já demonstramos não ser uma linguagem regular.
Assim, chegamos a uma contradição, e conclúımos que L não é uma linguagem regular.
3