Lista 2 - 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 2
(Linguagens Livres-do-Contexto)
Leitura necessária:
• Introdução à Teoria da Computação, 2a Edição (Michael Sipser):
– Caṕıtulo 2.1: Gramáticas Livres-do-Contexto
– Caṕıtulo 2.2: Autômato com Pilha
– Caṕıtulo 2.3: Linguagens Não-livres-do-contexto
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) Qual a definição formal de uma gramática livre-do-contexto?
Solução do professor: Uma gramática livre-do-contexto (GLC) é uma 4-tupla (V,Σ, R, S),
onde:
1. V é um conjunto finito denominado variáveis,
2. Σ é um conjunto finito, disjunto de V , denominado terminais,
3. R é um conjunto finito de regras, com cada regra sendo uma variável e uma cadeia de variáveis
e terminais, e
4. S ∈ V é uma variável inicial (ou variável de partida).
(b) O que é uma linguagem livre-do-contexto?
Solução do professor: Uma linguagem livre-do-contexto é uma linguagem que pode ser gerada
por uma gramática livre-do-contexto.
(c) O que significa dizer que uma gramática amb́ıgua? O que significa dizer que uma linguagem é
inerentemente amb́ıgua?
Solução do professor: Uma gramática G é amb́ıgua se ela gera alguma cadeia ambiguamente,
ou seja, se existe pelo menos uma cadeia w que possui duas ou mais derivações mais à esquerda
diferentes em G.
Uma linguagem L é inerentemente amb́ıgua se toda GLC para L é amb́ıgua (ou seja, se não é
posśıvel construir uma GLC não-amb́ıgua para L).
(d) Qual a definição formal de um autômato com pilha?
1
Solução do professor: Um autômato com pilha (AP) é uma 6-tupla (Q,Σ,Γ, δ, q0, F ), onde:
1. Q é um conjunto finito de estados,
2. Σ é o alfabeto (finito) de entrada,
3. Γ é o alfabeto (finito) de pilha,
4. δ : Q× Σ� × Γ� → P(Q× Γ�) é a função de transição (onde Σ� = Σ ∪ {�} e Γ� = Γ ∪ {�}),
5. q0 ∈ Q é o estado inicial, e
6. F ⊆ Q é o conjunto de estados de aceitação (ou estados finais).
(e) O que diz o lema do bombeamento para linguagens livres-do-contexto?
Solução do professor: O Lema do bombeamento (LB) para linguagens livres-do-contexto diz
que se A é uma linguagem livre do contexto, então existe um número p, chamado de comprimento
de bombeamento, tal que, se s é uma cadeia qualquer em A de comprimento pelo menos p, então
s pode ser divida em cinco partes
s = uvxyz
satisfazendo as seguintes condições:
1. para cada i ≥ 0, uvixyiz ∈ A,
2. |vy| > 0, e
3. |vxy| ≤ p.
(f) Explique como o lema do bombeamento para linguagens livres-do-contexto pode ser utilizado
para demonstrar que uma linguagem não é livre-do-contexto.
Solução do professor: Para usar o lema do bombeamento para linguagens livres-do-contexto
para mostrar que uma linguagem L não é livre-do-contexto:
1. Assuma que L seja livre-do-contexto.
2. Use o LB para garantir que existe um comprimento p tal que toda cadeia 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 = uvxyz (satisfazendo as condições do LB de que
|vy| > 0 e |vxy| ≤ p), existe pelo menos um valor de i tal que uvixyiz /∈ 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 livre-do-contexto.
Exerćıcios.
2. (Sipser 2.2)
(a) Use as linguagens A = {ambncn | m,n ≥ 0} e B = {anbncm | m,n ≥ 0} juntamente com
o Exemplo 2.36 (que mostra que a linguagem {anbncn | n ≥ 0} não é livre-do-contexto) para
mostrar que a classe das linguagens livres-do-contexto não é fechada sob interseção.
(b) Use a parte (a) e a lei de DeMorgan (Teorema 0.20) para mostrar que a classe de linguagens
livres-do-contexto não é fechada sob complementação.
2
Solução do professor:
(a) A linguagem A = {ambncn | m,n ≥ 0} é uma LLC, pois possui a seguinte GLC:
P →AY
A→ aA | �
Y → bY c | �
A linguagem B = {anbncm | m,n ≥ 0} é uma LLC, pois possui a seguinte GLC:
P →XC
X → aXb | �
C → cC | �
Mas a interseção delas é A ∩B = {anbncn | n ≥ 0}, que pelo Exemplo 2.36 sabemos não ser uma
LLC. Logo LLCs não são fechadas sob interseção.
(b) Vamos mostrar que a classe das LLCs não é fechada sob complementação. A prova é por con-
tradição.
Assuma que a classe das linguagens livres-do-contexto fosse fechada sob complementação.
Mas note que sabemos que LLCs são fechadas sob união, e sabemos que (por DeMorgan)
A ∩B = A ∪B.
Logo, se LLCs fossem fechadas sob complementação, elas também seriam fechadas sob interseção,
o que é um absurdo (já provamos que elas não são). Assim conclúımos que a classe das LLCs não
é fechada sob complementação.
3. (Sipser 2.3) Responda a cada item para a seguinte gramática livre-do-contexto G.
R→ XRX | S
S → aTb | bTa
T → XTX | X | �
X → a | b
(a) Quais são as variáveis de G?
(b) Quais são os terminais de G?
(c) Qual é a variável inicial de G?
(d) Dê três cadeias em L(G).
(e) Dê três cadeias que não estão em L(G).
(f) Verdadeiro ou Falso: T ⇒ aba.
(g) Verdadeiro ou Falso: T
∗⇒ aba.
(h) Verdadeiro ou Falso: T ⇒ T .
(i) Verdadeiro ou Falso: T
∗⇒ T .
(j) Verdadeiro ou Falso: XXX
∗⇒ aba.
(k) Verdadeiro ou Falso: X
∗⇒ aba.
(l) Verdadeiro ou Falso: T
∗⇒ XX.
(m) Verdadeiro ou Falso: T
∗⇒ XXX.
(n) Verdadeiro ou Falso: S
∗⇒ �.
(o) Dê uma descrição em português de L(G).
Solução do professor: Solução dada no livro-texto.
4. (Sipser 2.4 - itens (a), (d)) Dê gramáticas livres-do-contexto que gerem as seguintes linguagens. Em
todos os itens o alfabeto Σ é {0, 1}.
Obs: Também dê diagramas de estados de autômatos com pilha para estas linguagens.
(a) {w | w contém pelo menos três 1’s}.
(d) {w | o comprimento de w é ı́mpar e o śımbolo do meio é um 0}.
3
Solução do professor:
a) GLC: dada no livro-texto.
Diagrama do autômato com pilha dado na figura seguinte.
d) GLC: dada no livro-texto.
Diagrama do autômato com pilha dado na figura seguinte.
5. (Sipser 2.6 - itens (a), (c)) Dê gramáticas livres-do-contexto gerando as seguintes linguagens.
Obs: Também dê diagramas de estados de autômatos com pilha para estas linguagens.
(a) O conjunto de cadeias sobre o alfabeto {a, b} com mais a’s que b’s.
(c) {w#x | wR é uma subcadeia de x para w, x ∈ {0, 1}∗}
Solução do professor:
(a) GLC: dada no livro-texto.
Diagrama do autômato com pilha dado na figura seguinte.
(c) GLC: dada no livro-texto.
Diagrama do autômato com pilha dado na figura seguinte.
4
6. (Sipser 2.8) Mostre que a cadeia the girl touches the boy with the flower tem duas derivações
mais à esquerda diferentes na gramática G2 da página 107. Descreva em português os dois significados
diferentes dessa sentença.
Solução do professor: Dada no livro-texto.
7. (Sipser 2.11) Converta a GLC G4 dada no Exerćıcio 2.1 para um AP equivalente, usando o procedi-
mento dado no Teorema 2.20.
Solução do professor: Vide figura abaixo.
8. (Sipser 2.14) Converta a seguinte GLC numa GLC equivalente na forma normal de Chomsky, usando
o procedimento dado no Teorema 2.9.
A→ BAB | B | �
B → 00 | �
Solução do professor: Para colocar a seguinte GLC na forma normal de Chomsky
A→ BAB | B | �
B → 00 | �
nós seguimos os seguintes passos.
Primeiro adicionamos uma nova variável de partida:
S → A
A→ BAB | B | �
B → 00 | �
Eliminamos a regra B → �:
S → A
A→ BAB | B | � | AB | BA | A
B → 00
Eliminamos a regra A→ �:
S → A | �
A→ BAB | B | AB | BA | A | BB
B → 00
5
Eliminamos a regra inútil A→ A:
S → A | �
A→ BAB | B | AB | BA | BB
B → 00
Eliminamos a regra unitária A→ B:
S → A | �
A→ BAB | AB | BA | BB | 00
B → 00
Eliminamos a regra unitária S → A:
S → � | BAB | AB | BA | BB | 00
A→ BAB | AB | BA | BB | 00
B → 00
Inclúımos uma nova regra Z → 0:
S → � | BAB | AB | BA | BB | ZZ
A→ BAB | AB | BA | BB | ZZ
B → ZZ
Z → 0
Inclúımos uma nova regra U →BA:
S → � | UB | AB | BA | BB | ZZ
A→ UB | AB | BA | BB | ZZ
B → ZZ
Z → 0
U → BA
Note que a GLC acima está na forma normal de Chomsky pois toda regra ou tem exatamente duas
variáveis ou exatamente um terminal no lado direito, e a única regra � está na variável de partida.
9. (Sipser 2.16) Mostre que a classe de linguagens livres-do-contexto é fechada sob as operações regulares,
união, concatenação e estrela (fecho de Kleene).
Solução do professor: Solução dada nos slides da disciplina.
10. (Sipser 2.30 - itens (b) e (c)) Use o lema do bombeamento para mostrar que as seguintes linguagens
não são livres do contexto.
(b) {0n#02n#03n | n ≥ 0}
(c) {w#t | w é uma subcadeia de t, onde w, t ∈ {a, b}∗}
Solução do professor: Dada no livro-texto.
6