FEUP / LEIC TEORIA DA COMPUTAÇÃO

GABRIEL DAVID/CRISTINA RIBEIRO CFL - 1/1

EXERCÍCIOS DE LINGUAGENS SEM CONTEXTO 1 Desenhe um autómato de pilha determinista que aceite a linguagem

{0n1m 0n | n e m arbitrários}. 2 Nos autómatos de pilha que construiu em exercícios anteriores, teste o determinismo.

Verifique se são autómatos deterministas e, caso não o sejam, localize as transições que o invalidam.

3 Mostre, usando o lema da bombagem para as linguagens sem contexto, que a linguagem das cadeias da forma anbnci, em que n ≤ i ≤ 2n, não é uma linguagem sem contexto.

4 “Uma gramática sem contexto é ambígua se existir uma derivação mais à esquerda e uma derivação mais à direita de pelo menos uma das cadeias por ela reconhecidas”. Esta afirmação é verdadeira? Justifique.

5 “Dado um autómato de pilha não determinista, existe sempre um autómato determinista equivalente, ou seja, que reconhece exactamente a mesma linguagem.” Esta afirmação é verdadeira? Justifique.

6 Mostre, usando o lema da bombagem para as linguagens sem contexto, que a linguagem das cadeias da forma 0p, em que p é primo, não é uma linguagem sem contexto. [Nota: já provámos que esta linguagem não satisfaz o lema da bombagem para as linguagens regulares; usar uma estratégia semelhante para mostrar que não verifica este.]

7 Mostre, usando o lema da bombagem, que a linguagem das cadeias da forma 0i1j, em que j=i2, não é uma linguagem sem contexto.

8 Quando se tenta aplicar o lema da bombagem para as linguagens sem contexto a uma linguagem que é desta família tentando mostrar que não o é, acontece que o “adversário ganha” sempre, e não conseguimos completar a prova. Ilustre este processo com as linguagens L1= {00, 11} e L2= {0n1n, n≥1}.

9 Dadas 2 cadeias w e x, vamos chamar inter(w,x) ao conjunto de cadeias que se obtém intercalando símbolos de w e x pela ordem em que ocorrem em w e em x. Estende-se a operação para 2 linguagens L1 e L2, chamando inter(L1, L2) à união, para todos os pares de cadeias w de L1 e x de L2, de inter(w,x).

a) Determine o valor de inter(00,111). b) Determine o valor de inter(L1, L2) sendo L1= L(0*) e L2= {0n1n, n≥0}.

c) Mostre que se L1 e L2 forem ambas linguagens regulares, então inter(L1, L2) é uma linguagem regular. [Sugestão: considerar os DFA’s de L1 e L2.]

d) Mostre que se L é uma linguagem sem contexto e R uma linguagem regular, então inter(L, R) é uma linguagem sem contexto. [Sugestão: considerar um PDA para L e um DFA para R.]

10 Mostrar que numa gramática na forma normal de Chomsky todas as árvores de análise para cadeias de comprimento n têm 2n-1 nós interiores.