Exercicios aula28 comentados

Prévia do material em texto

1 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
Exercícios Associados à Aula 28 (27/11/2013) 
Feitos em sala e em equipes 
 
Questões do POSCOMP’2011 
 
 
 
A resposta certa está assinalada em vermelho. 
Por que é correta e por que as demais alternativas são incorretas? 
 
As justificativas para a correção/incorreção das respostas tem a ver com: 
• operações sobre conjuntos (união, interseção, concatenação) 
• entendimento dos tipos de linguagem no caso de L1 e L2 
• entendimento de que L1 é uma linguagem regular, onde as ocorrências de a,b,c são 
ordenadas porém independentes 
• entendimento de que L2 é uma linguagem livre de contexto e intrinsecamente não-
determinística uma vez que: ou as ocorrências de a,b são dependentes ou as 
ocorrências de b,c são dependentes; e que dependências do tipo “simetria” (caso da 
questão) entre duas sub-cadeias adjacentes caracterizam justamente estruturas 
relacionadas ao encaixe central, a propriedade que distingue as gramáticas livres de 
contexto das regulares. 
 
 
 
A resposta certa está assinalada em vermelho. 
Por que é correta e por que as demais alternativas são incorretas? 
 
As justificativas para a correção/incorreção das respostas tem a ver com: 
 
 2 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
• o entendimento de que cadeias reversas são um caso típico de linguagens sensíveis a 
contexto demonstrado pelo lema do bombeamento para linguagens livres de 
contexto 
• o entendimento de que pela hierarquia de linguagens (e seus correspondentes 
autômatos reconhecedores), exceto por especificidades das linguagens sensíveis a 
contexto no que diz respeito à ocorrência de cadeias vazias, “quem pode mais pode 
menos”, ou seja: linguagens, gramáticas e autômatos mais poderosos (gerais) sempre 
dão conta de (ou incluem) linguagens, gramáticas e autômatos mais poderosos 
(específicos) 
• o entendimento de que o autômato mais poderoso que há – máquina de Turing 
universal – aceita outras máquinas de Turing como entrada e, como pode haver 
máquinas de Turing não determinísticas, a universal deve poder ser, ela própria, não 
determinística 
 
Questão do POSCOMP’2009 
 
 
 
Qual a resposta correta? 
 
Obviamente a resposta “E” é a resposta falsa. Os conjuntos enumeráveis são os super-
conjuntos de todas as linguagens tratáveis por autômatos (no caso a máquina de Turing). 
Portanto, considerando que o propósito mesmo de LF&A é tratar de conjuntos infinitos 
através de uma especificação finita, a afirmativa de “E” é cabalmente incorreta. 
 
 3 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
Questão do POSCOMP’2008 
 
 
 
Qual a resposta correta? 
 
A afirmativa incorreta é “D”, que se fosse correta implicaria que o problema da parada não 
existe. 
Questão do ENADE’2008 
 
 
Que tipo de gramática aparece no enunciado da questão? 
Qual a resposta certa para a pergunta da prova? 
 
A gramática da questão se apresenta como uma gramática sensível a contexto, com mais de 
um símbolo terminal ocorrendo à esquerda da regra e nenhuma cadeia vazia à direita. Como 
pelas produções apresentadas o que se tem é uma sequencia a+ (um ou mais a) seguidas de B, 
que pode derivar apenas um único b. Ou seja a linguagem é a+.b, facilmente reconhecível 
como uma gramática regular. 
 
 4 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
Questões de Ramos(2009) 
 
 
A respeito do item (a): 
Partindo das sentenças (cadeias aceitáveis) compostas por terminais apenas, qualquer cadeia 
que consista de a ou b ou c ou seja vazia, pertence à linguagem. 
• Pela regra S � S*, qualquer cadeia composta por qualquer combinação de cadeias 
formadas sobre o alfabeto {a,b,c} -- (a,b,c)* -- pertence a L; 
• Pela regra S � “(“S””)” delimitar sentenças (a,b,c)* por parênteses resulta em cadeia 
pertencente a L, ou seja: “(“ (a,b,c)* “)” pertence a L 
• Pela regra S � S+S quaisquer duas cadeias de L separadas por “+” resultam em nova 
cadeia que pertence a L 
• Pela regra S � SS quaisquer duas cadeias concatenadas de L resultam em nova 
cadeia que pertence a L 
 
A respeito do item (b): 
• a cadeia vazia pertence à linguagem 
• como o símbolo “e” não está no vocabulário nenhuma cadeia que o contenha pertence 
à linguagem. O mesmo ocorre para o símbolo ‘|’. 
• a cadeia a*b(ca*+bcc)*+ε pode ser derivada por: 
o a*b(ca*+bcc)*+S se S� a*b(ca*+bcc)* 
o a*b(ca*+bcc)* se S � (ca*+bcc) 
o (ca*+bcc) se S � ca* e S � bcc 
o ca* se S � SS (ok) ou se S � S* (ok) 
o bcc se S � SS (ok) ou se S � S* (ok) 
o b(ca*+bcc) se S � SS ou S � S* (ok) 
o a*b... se S � SS ou S � S* (ok) 
• a cadeia (a*)* trivialmente pertence à linguagem, uma vez que a cadeia vazia é aceita. 
 
 
 
 
 5 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
 
 
 
(a) 
 
 
(b) movimentos do autômato para a cadeia “abaabceedd”: 
 
(q0,Z,abaabceedd) -> (q0,Z, baabceedd) -> (q0, BZ, aabceedd) -> (q0,BZ, abceedd) -> 
(q0,BZ, bceedd) -> (q0,BBZ, ceedd) -> (q1,BBZ, eedd) -> (q1,BBZ, edd) -> (q1,BBZ, dd) -> 
(q1,BZ, d) -> (q1,Z, ε) -> (q2, ε , ε) 
A cadeia é aceita pelo autômato. 
 
(c) A linguagem aceita pelo autômato é formada pelas cadeias w = (a|b)*c(e|d)* tais 
que |w|b = |w|d. 
 
 6 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
 
 
 
 
 
(a) Gramática livre de contexto 
(b) L(G) é uma linguagem do tipo 2 (livre de contexto). A linguagem não pode ser regular 
pelas características de balanceamento de símbolos como ‘(‘ e ‘)’, por exemplo. 
 
 
 
Para facilitar, vamos referenciar as gramáticas acima como G1, G2, G3 e G4, 
respectivamente. 
 
 
 7 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
G1: A gramática já está na FNC 
 
G2: 
S � AX | BY | c 
A� a 
B�b 
X�SA 
Y�SB 
 
G3: 
S�AX | AY | d 
A�a 
X�SB 
B�b 
Y�SC 
C�c 
 
G4: 
S�AX | BY | AB | BA 
A�a 
B�b 
X�SZ 
Z�BS 
Y�SW 
W�AS 
 
 
 
 8 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
 
 
Exemplo: (f) a2i, i ≥ 0 
i) exemplos de cadeias que pertencem à linguagem: aa, aaaa, aaaaaa, aaaaaaaa 
exemplos de cadeias que não pertencem à linguagem: a, aaa, aaaaa 
 
ii) GLC que gera a linguagem: 
S -> aSa | ε 
 
iii) Sequências de derivação: 
cadeia aa: S -> aSa -> aa 
cadeia aaaa: S -> aSa -> aaSaa -> aaaa 
 
iv) Árvores de derivação: 
 
 S S 
 / | \ / | \ 
 a S a a S a 
 | / | \ 
 ε a S a 
 | 
 ε 
 
v) Autômato de pilha 
 
 
 
vi) Sequências de configurações para reconhecimento da cadeia ‘aaaa’. Lembrar que, como o 
APD acima é não-determinístico, outras transições seriam possíveis, mas não levariam ao 
reconhecimento da cadeia de entrada. 
 
(q0,Z,aaaa) -> (q1,SZ,aaaa) -> (q1,aSaZ,aaaa) -> (q1,SaZ,aaa) -> (q1,aSaaZ,aaa) -> (q1,SaaZ,aa) 
-> (q1,aaZ,aa) -> (q1,aZ,a) -> (q1,Z, ε) -> (q2, ε, ε) 
 
 
 
 9 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
 
(a) exemplo de gramática: 
S � aBbC | aYc | D 
B� aBb | ε 
C� cC | ε 
D� dD | ε 
Y� aYc | Z 
Z� bZ | ε 
 
(b) autômato de pilha 
 
 
 
 
 
Para resolver essa questão, podemos aplicar o lema do bombeamento para linguagens livres 
de contexto e provar que as linguagens não satisfazem as condições do lema. 
 
No item (a), por exemplo, a aplicação do lema poderia ser como a seguir: 
 
Assumindo que a linguagem é livre de contexto, existe um inteiro p que corresponde ao 
comprimento mínimo das cadeias que satisfazem o lema do bombeamento de linguagens livres 
de contexto. 
 
 10 
IIIIIIIINNNNNNNNFFFFFFFF11111111666666662222222266666666 LLLLLLLLiiiiiiiinnnnnnnngggggggguuuuuuuuaaaaaaaaggggggggeeeeeeeennnnnnnnssssssss FFFFFFFFoooooooorrrrrrrrmmmmmmmmaaaaaaaaiiiiiiiissssssss eeeeeeee AAAAAAAAuuuuuuuuttttttttôôôôôôôômmmmmmmmaaaaaaaattttttttoooooooossssssss ((((((((22222222000000001111111133333333--------22222222)))))))) Informática 
PUC-Rio 
Seja w = apbpcp. A cadeia ww = apbpcp apbpcp pertence à linguagem, por definição. O lema do 
bombeamento diz que toda cadeia pode ser dividida em 5 partes, uvxyz, tais que |vxy| ≤ p e 
|vy| ≥ 1, de modo que, para todo i ≥ 0, a cadeia uvixyiz deve sempre pertencer à linguagem. 
 
Entretanto, a cadeia central do bombeamento (vxy) deve ter comprimento menor ou igual a p. 
No caso da cadeia ww escolhida, vxy só pode ser formada por um único símbolo (a, b ou c), ou 
por sequências formadas por apenas dois símbolos (a’s e b’s, b’s e c’s, c’s e a’s, e assim por 
diante). Portanto, em qualquer caso, o bombeamento de v e y irá conter apenas um ou dois 
símbolos distintos, e irá desbalancear as duas metades da cadeia resultante que, portanto, 
não irá pertencer à linguagem. Assim, como o lema do bombeamento não se aplica, a 
linguagem não pode ser livre de contexto. 
 
 
A lembrar 
Através de que operações os AP’s preservam ou alteram a pilha. 
• preservar é ler (pop) e gravar (push) o mesmo símbolo, sem qualquer outro. 
• alterar é consumir (ler e não gravar nada na pilha) ou empilhar (push) um novo 
elemento 
Os símbolos terminais sempre consomem a pilha. 
Símbolos que apareçam à direita das regras de produção sempre são “empilhados”.