EX GLC AP MT

Prévia do material em texto

Lista de Exercícios 3 
 
 
 
1) Mostre três cadeias de tamanho maior ou igual a quatro que podem ser geradas pela 
gramática livre de contexto abaixo: 
 
G1 = ({S,J,P,D,E}, {1,2,.}, P1, S), 
onde P1 é o conjunto de produções: 
 
 
 
2) Diga se a gramática livre de contexto G2 gera as cadeias abaixo. Construa uma de-
rivação e uma árvore de derivação para as cadeias que a gramática puder gerar. 
 
G2 = ({S,T}, {a,b}, P2, S), 
onde P2 é o conjunto de produções: 
 
 
a) ε 
b) aba 
c) baa 
d) abba 
e) aabb 
 
 S → aSa 
| bSb 
| T 
 T → a 
 | b 
 | ε 
 
 
S → J 
J → 1J | 2J | ε | P 
P → .D 
D → 1E | 2E 
E → 1E | 2E | ε 
 
3) Uma gramática é dita ambígua sse (se e somente se) for possível criar duas árvores 
de derivação para uma mesma cadeia terminal. Prove que a gramática livre de con-
texto G4 definida abaixo1 é uma gramática ambígua. (). 
 
 
 
 
4) Na gramática livre de contexto abaixo, considere que os não-terminais são os nomes 
entre os símbolos “<” e “>” e que, nas produções, ao invés da seta (→), são usados 
a seqüência de símbolos: dois-pointos, dois-pontos, igual (::=). Essa é a formatação 
conhecida como notação BNF. Com base na gramática abaixo G6, dada nessa no-
tação, resolva as questões: 
 
 
 
a) Dê um exemplo de derivação de uma cadeia na gramática acima que use ao 
menos um <comando>. 
b) Mostre uma árvore de derivação para a cadeia. 
c) Prove que a gramática acima é ambígua. 
 
 
1
 A partir de agora daremos apenas as produções da gramática. Em geral, as letras maiúsculas serão não-
terminais e o não-terminal no lado esquerdo (cabeça) da primeira produção será o não-terminal de início. 
G4: 
 S → Xc 
 | aY 
X → aXb 
 | ε 
Y → bYc 
 | ε 
G6: 
 
<programa> ::= <lista_decl> 
 
<lista_decl> ::= <declaracao> <lista_decl> 
 | <declaracao> 
 
<declaracao> ::= <tipo> <nome> ; 
 | func <nome> () { <comando> } 
 
<tipo> ::= int | char 
 
<comando> ::= <nome> = <expr> ; 
 | return <expr> ; 
 
<expr> ::= <expr> + <expr> 
 | <expr> * <expr> 
 | <nome> 
 
<nome> ::= aux | temp | x 
 
 
5) Abaixo, mostramos um exemplo de AP não-determinístico para reconhecer palavras 
na forma w.wr, ou seja, palavras cuja segunda metade (wr) é o reverso da primeira 
metade (w). Para cada cadeia abaixo, encontre alguma computação que comprove 
que ela é aceita pelo autômato. 
 
 
a) aa 
b) abba 
c) bbbb 
 
 
6) O Autômato com Pilha abaixo reconhece as cadeias sobre o alfabeto {a, b} que 
têm a mesma quantidade de a’s e de b’s. Mostre, nesse autômato, uma computação 
de aceitação para cada uma das cadeias dadas (todas são aceitas): 
 
 
a) ba 
b) aabb 
c) baba 
d) bbabaa 
 
 
7) Converta as gramáticas das questões 2 e 3 para Autômatos com Pilha equivalentes. 
 
 
8) Considerando que a Máquina de Turing dada a seguir tem {a,b,c} como alfabeto 
de entrada e que usa L para representar “esquerda” (left) e R para representar “di-
reita” (right), resolva as questões: 
 
a) Mostre a computação da cadeia “aabc”. Diga se a cadeia é ou não reconhe-
cida e justifique. 
b) Mostre a computação da cadeia “aabbcc”. Diga se a cadeia é ou não reco-
nhecida e justifique. 
c) Cite um exemplo de cadeia reconhecida e um exemplo de cadeia não reco-
nhecida pela MT dada. (Não pode citar as cadeias anteriores). 
d) Descreva informalmente a linguagem que ela reconhece. 
 
 
 
9) Considerando a Máquina de Turing abaixo, que tem {a,b} como alfabeto de en-
trada, responda: 
 
a) Mostre o estado e a fita a cada passo do processo de reconhecimento da ca-
deia “bab”. Ao final, diga se a palavra é ou não reconhecida e justifique. 
b) Dê dois exemplos de cadeias da linguagem dessa MT e dois exemplos de ca-
deias que não são da linguagem dessa MT. 
 
 
10) Sobre os diferentes modelos computacionais que estudamos, responda: 
 
a) Quais os nomes dos modelos. 
b) Qual o mais poderoso dos modelos? Como são chamadas as linguagens que 
podem ser representadas com esse modelo? 
c) Qual o menos poderoso? Como são chamadas as linguagens que podem ser 
representadas com esse modelo? 
 
 
11) O que é um problema de decisão? O que esse tipo de problema tem a ver com o 
conceito formal de linguagens? 
 
 
12) Quando um problema de decisão é classificado como decidível? 
 
 
13) Prove que é decidível o problema de testar se um número representado na forma 
decimal (dígitos de 0 a 9) é par. Prove isso de maneira clara, construindo uma Má-
quina de Turing. 
 
 
14) Crie uma gramática livre de contexto em notação BNF para gerar uma seqüência 
de expressões numéricas separadas por ponto-e-vírgula. Considere que os números 
da expressão tenham um só dígito de 0 a 9. As operações permitidas serão apenas 
adição (+) e multiplicação (*). Exemplos de cadeias que a sua gramática deve gerar 
são: “3”, “1+2*3;7+9”, “2+1;3;4+3+2;2;5*1”. 
 
 
15) Construa uma gramática livre de contexto, usando a notação BNF, para especificar 
a sintaxe da linguagem de programação descrita informalmente abaixo: 
 
a. Um programa é composto de um ou mais procedimentos. 
b. Cada procedimento é definido assim: 
• Inicia com a palavra “proc” 
• Depois vem um identificador 
• Depois vem um bloco 
c. Um identificador pode ser qualquer palavra formada apenas por letras 
(uma ou mais). 
d. Assuma que as letras podem ir apenas de ‘a’ a ‘d’. 
e. Um bloco 
• Inicia com “[[“ 
• Depois vem uma seqüência de comandos, possivelmente vazia 
• Termina com “]]” 
f. Um comando é definido assim: 
• Ou a palavra “var” seguida de um identificador seguido de “;” 
(representa uma declaração de variável). 
• Ou um identificador seguido de “<-” seguido de uma expres-
são seguida de “;” (representa uma atribuição). 
• Ou um identificador seguido da cadeia “();” (representa uma 
chamada de procedimento). 
g. Uma expressão é definida assim: 
• Uma expressão seguida de “*” seguida de outra expressão. 
• Ou “-“ seguido de uma expressão 
• Ou simplesmente a cadeia “41”. 
• Ou simplesmente um identificador. 
 
 
16) Dê um exemplo de cadeia que possa ser gerada pela gramática que você deu como 
resposta para a questão anterior. A cadeia deve usar ao menos um comando. Mostre 
também uma árvore de derivação para a cadeia. 
 
 
17) Dê uma explicação razoável (um esboço de uma prova matemática) para justificar 
que os seguintes problemas são decidíveis: 
 
a) Testar se um dado AFD M aceita a cadeia vazia. 
b) Testar se um dado AFN M aceita a cadeia vazia. 
c) Testar se um dado AFD M aceita uma cadeia qualquer w. 
d) Testar se uma dada expressão regular R gera uma cadeia dada w. 
e) Testar se um dado AFD M representa a linguagem vazia (ou seja, testar se M 
não aceita nenhuma cadeia). 
f) Testar se uma dada GLC G representa a linguagem vazia (ou seja, testar se G 
não gera nenhuma cadeia). 
 
 
18) Dê uma explicação razoável (um esboço de uma prova matemática) para justificar 
que os seguintes problemas são indecidíveis: 
 
a) Testar se uma dada MT M aceita uma cadeia de entrada w. 
b) Testar se uma dada MT M vai parar (ou seja, não vai entrar em loop) quando 
receber uma cadeia w como entrada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
“Aquele que habita no abrigo do Altíssimo e descansa 
à sombra do Todo-poderoso pode dizer ao Senhor: 
Tu és o meu refúgio e a minha fortaleza, 
o meu Deus, em quem confio. 
Ele o livrará do laço do caçador e do veneno mortal. 
Ele o cobrirá com as suas penas, 
e sob as suas asas você encontrará refúgio; 
a fidelidade dele será o seu escudo protetor.”(Salmos 91:1-4)