Fundamentos da Teoria da Computação
Professor: Newton José Vieira
Terceira Prova Turma N
Duração:
1o semestre de 2012
DCC/ICEx/UFMG
05/06/2012
1 hora e 30 minutos.
4 pontos.
Valor de cada questão:
1. Construa:
(a) um APD que reconheça {0m 1n | m < n};
(b) um APN que reconheça {0m 1n | m > n}.
2. Construa GLCs que gerem as linguagens:
(a) L1 = {am bn | m > n}.
(b) L2 = {bm cn | m < n}.
(c) L1 ((L2 L1 ) ∪ L∗2 ).
3. Ainda sobre GLCs:
(a) Mostre que a GLC
P → A|B
A → aAa | λ
B → bBb | λ
é ambígua. Construa uma GLC equivalente não ambígua.
(b) Obtenha uma GLC na FNC equivalente a:
P
A
B
C
→
→
→
→
ABC
aA | BC | a
bBb | C
abc | A | λ
4. Prove que se L não é LLC e é retirado um conjunto nito de palavras de L, a linguagem
resultante não é LLC. Use isso para provar que
{ak bk ck | k > 1010 }
não é uma linguagem livre do contexto.
• APN: autômato de pilha não determinístico.
• APD: autômato de piliha determinístico.
• GLC: gramática livro do contexto.
• LLC: linguagem livre do contexto.
• FNC: forma normal de Chomsky.