Lista 2 - Linguagens Livres-do-Contexto

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 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?
(b) O que é uma linguagem livre-do-contexto?
(c) O que significa dizer que uma gramática amb́ıgua? O que significa dizer que uma linguagem é
inerentemente amb́ıgua?
(d) Qual a definição formal de um autômato com pilha?
(e) O que diz o lema do bombeamento para linguagens livres-do-contexto?
(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.
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.
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).
1
(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).
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}.
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}∗}
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.
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.
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 | �
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).
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}∗}
2