Lista 1 3 - Linguagens Não Regulares

Prévia do material em texto

Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da
Computação 2021/2
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?
(b) Explique como o lema do bombeamento pode ser utilizado para demonstrar que uma linguagem
não é 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.)
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.
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.
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?
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.)
1