Lista 3 de Linguagens Formais e Autômatos
Profs. Alexandre Rademaker e Bruno Lopes
outubro de 2012
Justifique as suas respostas sempre.
Questões:
1
Lema do Bombeamento
1. A linguagem L = {ak bk cn /0 ≤ k ≤ 1000 e n > 0} é regular. No entanto,
Deivid Pé Torto, usando o lema do bombeamento, obteve a seguinte prova
de que L não é regular. Aponte o erro na prova de Deivid Pé Torto e
argumente que a linguagem é de fato regular.
Suponho que L é regular, então vale o lema do bombeamento.
Isto é, existe um número positivo m tal que para qualquer palavra ω de L com tamanho maior que m, tem-se u,v e z, tal que ,
ω = uvz, |uv| ≤ m, |v| > 0 e para todo i ∈ N at, uv i z ∈ L. Ora,
a900 b900 cm tem tamanho maior que m, então, uv só tem a’s e
portanto uv 0 z que é o mesmo que uz é da forma a900−r b900 cm
com r > 0. Como a900−r b900 cm 6∈ L, temos a conclusão desejada.
2. Usando o lema de bombeamento para linguagens regulares, prove que
a linguagem das palavras ω sobre {a, b, c, d} com a mesmo número de
ocorrências de cada um dos sı́mbolos em ω não é regular.
3. Usando o lema do bombeamento para linguagens regulares, prove que
{ap /p é primo} não é regular. Dica: Um número não é primo se pode ser
expresso como a multiplicação de dois números, ambos diferentes de 1.
Escolha um primo p maior que k e mostre que uv h z, com h = kuk + kzk,
mostrando que o resultado so bombeamento não pertence a linguagem.
4. Já sabemos, inclusive pelo ı́tem acima, que a linguagem LnP = {ap /p não é primo}
não é regular, pois é o completemento em relação a {a}∗ de uma linguagem que não é regular. Pede-se provar, diretamente via o uso do lema do
bombeamento, que LnP não é regular.
1
5. As questões abaixo são resolvidas com a aplicação direta do lema do bombeamento. Escolha uma palavra dependendo de k , do lema do bombeamento, e mostre que existe um bombeamento da decomposição uvz que
não pertence a linguagem.
(a) {an bn /n ∈ N at} Dica: escolha ak bk e mostre que uv 0 z não pertence
a linguagem.
(b) {an bm /n > m} Dica: escolga ak+1 bk e mostre que uv 0 z não pertence
a linguagem.
m
(c) {an /n ∈ N at}, com m fixo, ou seja considere uma linguagem para
m
cada m. Dica: escolha ak e mostre que uv 2 z não pertence a linguagem.
(d) {ww/w ∈ {a, b}? } Dica: escolha ak bk ak bk e mostre que uv 0 z não
pertence a linguagem.
(e) (Difı́cil) {w1 w2 /w1 6= w2 , wi ∈ {a, b}? }.
2
Linguagens Livres de Contexto
1. Considere a seguinte gramática para expressões aritméticas sobre os identificadores “a” e “b’.
E -> E + T | T
T -> T * F | F
F -> (E) | a | b | c
• Defina um autômato de pilha que aceite a linguagem das expressões
aritméticas. Dica: Utilize a gramática acima para construir o APND.
• Exiba duas árvores de derivação distintas para a palavra a+b*a.
Dica: Identifique duas derivações mais a esquerda distintas.
• O que deve ser feito para que o APND do ı́tem acima não possuir
transições (empilhamento ou desempilhamento sem leitura, ou lendo
)? Justifique com exemplo. Dica: Retire recursões mais a esquerda.
2. Considere a seguinte gramática para comando em uma linguagem de programação, onde E refere-se ao não-terminal da gramática da questão
acima.
C -> if V then C | if V then C else C | V = E
V -> a | b | c
(a) Exiba duas árvores de derivação distintas para a palavra abaixo mostrando que a gramática é ambı́gua.
if a then if b then c=a else b=c
2
(b) A gramática abaixo não é ambigua e gera a mesma linguagem gerada
pela gramática acima. De fato ela retira a ambiguidade da mesma
de forma a associar cada else com o then “mais próximo’ ainda
não associado. Explique como isso foi possı́vel em termos puramente
gramaticais.
C -> A | N
A -> if V then A else A | V = E
N -> if V then C | if V then A else N
3. Marque (V) ou (F) justificando:
• A união de linguagens geradas por gramática é gerada por gramática
também.
• A união de Linguagens Livres de Contexto é Livre de Contexto.
• Toda linguagem LLC pode ser aceita por um APND com somente
um estado.
• Se uma L ⊆ Σ∗ é livre de contexto então seu complementar em
relação a Σ, ou seja Σ∗ − L também é LC.
• As linguagens sensı́veis ao contexto1 nem sempre são decidı́veis2
• Toda linguagem regular é aceita por um autômato de pilha determinı́stico.
4. Apresente gramáticas livres de contexto para gerar cada uma das linguagens abaixo:
(a) {an b3n /n ∈
N}. Dica: é uma variação da gramática para anbn.
(b) {an bm /n < m}. Dica: A linguagem é concatenação de uma regular
e an bn .
(c) {an bm /m < n}. Dica: Veja dica acima.
(d) {an bm /m 6= n}. Este é mais difı́cil que os outros.
(e) A linguagem das palavras com a e b, onde o número de ocorrência
de a’s e b’s é igual.
5. Se L1 e L2 são livres de contexto, mostre que L1 ◦ L2 e L?1 são livres de
contexto.
BOA LISTA
1 Geradas
por gramáticas onde todas as regras γ1 → γ2 , são tais que |γ1 | ≤ |γ2 |
que uma linguagem é decidı́vel se existe um programa capaz de reconhecê-la,
isto é, determinar as palavras que pertencem e as que não pertencem a mesma
2 Lembre-se
3