Lista1 3_LingNaoRegulares[solucao] FTC UFMG LISTA

Prévia do material em texto

Área de Teoria DCC/UFMG Fundamentos de Teoria da Computação 2020/01
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 1 - Parte 3/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
partes,
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)
1
Solução do professor:
a) Solução dada no livro-texto.
b) Vamos provar por contradição. Assuma que A2 = {www | w ∈ {a, b}∗} seja uma linguagem
regular. Seja p a constante de bombeamento dada pelo lema do bombeamento. Escolha a palavra
s como sendo apbpapbpapbp (ou seja, s = www para w = apbp). Como s ∈ A2 e |s| ≥ p, o LB diz
que se pode dividir s em três partes s = xyz, onde para qualquer i ≥ 0, xyiz ∈ A2 (que é a primeira
condição do LB). A segunda condição do LB (|xy| ≤ p) nos garante y só pode conter a’s, uma vez
que s começa com p ocorrências de a. Além disso, a terceira condição do LB (|y| > 0) garante
que y tem ao menos um a. Isso quer dizer que x = a|x| (para |x| ≥ 0), y = a|y| (para |y| > 0),
e z = ap−|x|−|y|bpapbpapbp. Logo xy2z = a|x|a|y|a|y|ap−|x|−|y|bpapbpapbp = ap+|y|bpapbpapbp, que
é uma cadeia que não pertence a A2 (pois |y| > 0). Mas isto viola a primeira condição do LB, e
chegamos a uma contradição. Portanto conclúımos que A2 não é uma linguagem regular.
c) Solução dada no livro-texto.
3. (Sipser 1.30)
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 prova estamos interessados em mostrar que uma linguagem diferente, no caso, 0∗1∗
não é regular. O erro da prova é 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∗. Por isso não podemos concluir que 0∗1∗ não é regular, e a prova está
errada.
4. (Sipser 1.48)
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.
Solução do exerćıcio 1.48
5. (Sipser 1.49 - Itens (a) e (b))
Além disso, responda ao seguinte item (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 provar 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!
3