P1 - 2013.2 - Gabarito (Prof. Clarisse)

Prévia do material em texto

P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 1 
 
Prova 1 de INF1626 – Linguagens Formais e Autômatos 
Aluno(a): 
Matrícula: 
 
Atenção: O tempo total de prova é de 110 minutos (09:05 às 10:55). Durante a prova não é permitido 
o uso de qualquer aparelho eletrônico (por exemplo: telefone celular, iPod ou MP3 Player, Tablets, 
etc.). Se alguém insistir em usar um, sua prova será anulada. 
 
Os alunos não devem se ausentar da sala durante a prova. Caso isto ocorra, o(a) professor(a) terá a 
opção de acatar ou não as questões respondidas após o retorno do aluno à sala. 
As provas só podem ser entregues depois de decorridos 45 minutos do tempo de realização. 
 
Pedidos de revisão de questões feitas a lápis poderão ser acatados ou não, dependendo do estado do 
manuscrito de prova. Qualquer pedido de revisão deve ser apresentado por escrito, conforme tiver sido 
comunicado à turma em sala de aula ou por email. 
 
Boa prova a todos! 
 
1. [1 Ponto] Classifique as seguintes gramáticas pela Hierarquia de Chomsky. 
(Tipo 3: Regular; Tipo 2: Livre de Contexto; Tipo 1 Sensível a Contexto; Tipo 0: Irrestrita) 
 
a. Gramática 1 
S � aA 
A � aS A � aB 
B � bC 
C � bD 
D � b D � bB 
Tipo 3 (Regular) 
 
b. Gramática 2 
S � aS S � aAbb 
A � ε A �aAbb 
Tipo 2 (Livre de contexto) 
 
c. Gramática 3 
S � XYZ S � aB 
B � PQ B � S 
Z � aS 
Tipo 2 (Livre de contexto) 
 
d. Gramática 4 
S � ε 
Tipo 3 (Regular) 
 
e. Gramática 5 
S � aSb S � AB S � SC 
A � Ab A � a 
B � bB B � b 
bC � C 
C � c 
Tipo 0 (Irrestrita) 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 2 
 
2. [1 Ponto] A Gramática 2 tem duas regras cujos lados direitos são exatamente 
iguais: 
S � aAbb e A � aAbb. 
Se eliminássemos a regra A � aAbb da Gramática 2, geraríamos exatamente a 
mesma linguagem que a Gramática 2 original gera? (S/N) Por quê? 
 
Houve dois tipos de erro nesta questão: 
1) Alunos que não perceberam que a retirada da regra A � aAbb faz a linguagem 
gerar cadeias muito diferentes. Confiram: 
 
Gramática 2 "original" 
S � aS 
S � aAbb 
A � aAbb 
A � ε 
Gera por exemplo cadeias do tipo a(aA(aA(aAbb)bb)bb) que combinadas com as 
derivações de S � aS, por exemplo aS(aS(aS(aS))), nos permitem ver que o 
padrão de cadeias da linguagem original é a+(bb)+ . 
 
Gramática 2 "modificada" 
S � aS 
S � aAbb 
A � ε 
Gera por exemplo cadeias do tipo aεbb que combinadas com as derivações de S � 
aS, por exemplo aS(aS(aS(aS))), nos permitem ver que o padrão de cadeias da 
linguagem original é a+bb . 
 
 O que se perde é a recursão de 1 a infinitos 'sufixos' bb ao final das cadeias da 
linguagem. Teremos sempre um sufixo único bb. 
 
2) Alunos que confundiram o que é uma linguagem ter INFINITAS CADEIAS 
(que tanto a G2 original garante, quanto a G2 modificada também), com as 
CADEIAS SEREM "INFINITAS" (i.e. terem tamanho infinito, o que não é 
possível). TODA CADEIA de TODA linguagem tem de ser FINITA. O que é 
infinito é o NÚMERO de cadeias da linguagem (cardinalidade do conjunto da 
linguagem e não o módulo de suas cadeias). Uma "cadeia infinita" seria uma 
cadeia que não termina nunca de ser derivada (logo, uma contradição com a noção 
de boa formação gramatical). 
 
3. [1 Ponto] Há autômatos finitos correspondentes às Gramáticas 1 e 5? 
Caso haja, quais são eles? 
(Para responder “quais são”, DESENHE os autômatos cabíveis.) 
 
Exemplos de Derivações de G1 
As regras S � aA, A � aS e A � aB geram aA(aS(aA(aS(aA(aS...aA(aB...)))))) 
= (aa)+ ... 
As regras B � bC, C � bD, D � b e D � bB geram 
...bC(bD(bB(bC(bD(bB...bC(bD(b))))))) = (bbb)+ 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 3 
 
Resposta: qualquer autômato que aceite um número n>1 de aa e m>1 de bbb, 
(aa)+(bbb)+ 
 
Exemplo de autômato correspondente a G1 
 
 
A G5 é uma Gramática Irrestrita (que contém não apenas regras de transformação 
estrutural do tipo bC � C, como também regras com mais de um não terminal no 
lado direito da produção, do tipo S � AB). 
 
Na aula 4, em que tratamos da Hierarquia de Chomsky, foi demonstrado em sala, 
com o JFLAP, como os autômatos correspondentes a linguagens de tipo mais 
complexo que as regulares correspondem a autômatos que não são autômatos 
finitos. Nos slides da aula damos um exemplo, para linguagem livre de contexto. 
Os autômatos inclusive usam memória auxiliar. Logo, a G5 não tem autômato 
finito correspondente. 
 
Houve quem tentasse apresentar um AF que reconhece cadeias com os mesmos 
terminais que os terminais das estruturas geradas por G5. O problema -- como 
discutido em aula -- é que a ESTRUTURA da cadeia no caso da linguagem 
regular, não tem nada a ver com a ESTRUTURA (árvore ou grafo de derivação) 
da cadeia no caso da linguagem irrestrita. 
 
4. [1 Ponto] A especificação formal de RECONHECEDORES (mecanismos de 
decisão sobre se cadeias de símbolos pertencem ou não a determinada linguagem 
a eles associadas) inclui, centralmente, a especificação de: 
a. Um estado inicial q0 
b. Um conjunto de estados finais F 
c. Um conjunto Γ de transições na forma de tuplas (qi, σ, qj) onde 
i. qi é o estado corrente, em que o autômato se encontra 
ii. σ é um símbolo lido na fita de entrada 
iii. qj é o estado destino, para o qual o autômato do reconhecedor 
transiciona (i.e. ‘vai para’) se lê, na fita de entrada, o símbolo σ 
 
Se, na especificação de um autômato A, qualquer, Γ possui duas tuplas 
iniciadas pelo mesmo estado qi – (qi, _, _) e (qi, _, _), onde ‘_’ é apenas um 
marcador genérico da ocorrência de um elemento da tupla (símbolo ou estado) 
– isto é necessariamente um indicador de que A é um autômato não 
determinístico? (S/N) Por quê? 
 
Dica: Tudo o que sabemos é que as duas tuplas em questão começam pelo mesmo 
estado corrente (qi). Nada sabemos sobre que símbolos ou que estados destino 
aparecem nas outras duas posições de cada tupla. 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 4 
 
Não. Para o autômato ser não determinístico, é necessário que haja pelo menos 
duas tuplas que indicam transição de um mesmo estado para estados diferentes 
com base no mesmo símbolo de entrada. 
Ou seja, para ser um indicador de que é um AFND, devem existir pelo menos 
duas tuplas (qi, σ1, qj) e (qi, σ2, qk) em Γ tais que σ1=σ2 e qj ≠ qk. 
 
5. [1 Ponto] Considere os seguintes trechos de código em Ruby, em que são 
implementados dois autômatos finitos determinísticos, A1 e A2. 
 
 
 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 5 
 
a. Os dois reconhecem a cadeia “aaaab”? (S/N) Mostre por que a reconhecem 
ou não, apresentando a sequência de transições do Autômato A1 e do 
Autômato A2, ao processarem a cadeia em questão. 
 
Sugestão: use uma tabela semelhante à Tabela 1, a seguir. 
 
Autômato A1 
 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 “a” <preencha> avança para o 
próximo símbolo 
 
 
 
 
 
Autômato A2 
 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 “a” <preencha> avança para o 
próximo símbolo 
 
 
 
 
 
Autômato A1 
 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “b” q2 Fim da entrada 
 
A1 aceita a cadeia “aaaab” pois a execução termina em q2, que é um 
estado final, e toda a entrada foi consumida. 
 
Autômato A2 
 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “a” q1 avança para o 
próximo símbolo 
q1 “b” q2 Fim da entrada 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 6 
 
 
A2 aceita a cadeia “aaaab” pois a execuçãotermina em q2, que é um 
estado final, e toda a entrada foi consumida. 
 
b. A1 reconhece “aaaa”? E A2? 
Como “aaaa” é um prefixo da cadeia do item anterior, podemos usar as 
mesmas tabelas como base para responder este item. 
A1 não aceita a cadeia “aaaa” porque a execução termina em q1, que não é um 
estado final. 
A2 aceita a cadeia “aaaa”, pois termina a sua execução no estado q1, que é 
final, e consome toda a cadeia de entrada. 
 
c. Algum dos dois autômatos reconhece ε? (S/N) Por quê? 
A2 reconhece ε, pois seu estado inicial q0 é também um estado final. 
 
Alguns alunos disseram que nenhum dos dois autômatos reconhece a cadeia 
vazia porque o símbolo correspondente à cadeia vazia não está definido nas 
transições de nenhum deles. Ora, não apenas o mero fato de o estado inicial 
ser também um estado final garante que este autômato aceita qualquer coisa 
(inclusive a cadeia vazia), como também era esperado que os alunos tivessem 
estudado as implementações dos autômatos em Ruby, sabendo como 
representar a cadeia vazia, como oferecê-la como entrada, etc. Este tipo de 
estudo teria dado noção de como a implementação funciona e como é 
processada a cadeia vazia. 
 
6. [1 Ponto] Sejam as seguintes linguagens abaixo definidas: 
• L1 contém cadeias w | w = a*b+ 
• L2 contém cadeias w | w = anbn e n ≥ 0 
• L3 contém cadeias w | w ∈ {a,b}* 
• L4 contém cadeias w | w = (ab)* 
 
Assinale se as afirmativas a seguir são verdadeiras (V) ou falsas (F) e diga por 
quê. (Atenção: a ausência da resposta para “por quê” implica pontuação nula para 
o item correspondente.) 
 
a. L1 ⊆ L3 (V/F) Por quê? 
V. L3 contém todas as cadeias possíveis de serem formadas com o alfabeto {a,b}, 
o que inclui as cadeias de L1. 
 
b. L2 = L4 (V/F) Por quê? 
F. Contra-exemplos: a cadeia “aabb” pertence a L2 e não pertence a L4, “abab” 
pertence a L4 e não pertence a L2. 
 
c. L2 ⊆ L3 (V/F) Por quê? 
V. O argumento é o mesmo do item a. 
 
d. L3 ∩ L4 = ∅ (V/F) Por quê? 
F. Novamente usando o argumento do item (a), todas as cadeias de L4 pertencem 
a L3, ou seja, L4 ⊂ L3. Portanto, L3 ∩ L4 = L4. 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 7 
 
 
e. L1 ∪ L2 = L3 (V/F) Por quê? 
F. Contra-exemplo: a cadeia “abab” não pertence a L1 nem a L2, mas pertence a 
L3. 
 
Comentário: Nesta questão apareceu bastante gente derrapando na notação, 
confundindo representação de cadeias e concatenações entre elas com a notação 
de “conjuntos de cadeias (e concatenações entre elas)”. A partir daí, todas as 
operações sobre conjuntos foram sacrificadas nas resposta. Além disto, houve 
quem não percebesse que a linguagem L3 é o fechamento reflexivo e transitivo do 
alfabeto {a,b}, que por definição inclui todas as concatenações possíveis de “a”s e 
“b”s, inclusive a concatenação nula (cadeia vazia), o que tornava a resposta de 4 
dos 5 itens da questão 6 extremamente simples e rápida. 
 
Recomenda-se fortemente aos alunos que obtiveram menos do 60% da pontuação 
total desta questão que revisitem os fundamentos de teoria de conjuntos e as 
definições de fechamento reflexivo e transitivo de um alfabeto de símbolos. 
 
7. [1 Ponto] Construa uma Gramática Regular e um Autômato Finito a ela 
equivalente que definam uma linguagem L tal que as cadeias que a ela pertencem 
são formadas de acordo com a expressão x j : j > 0 e j / 3 = n + r para n > 0 e r ≠ 0. 
(Atenção: “x” é a única letra do alfabeto de L.) 
 
Nesta questão, aceitamos diferentes interpretações consistentes apresentadas pelos 
alunos. Primeira, a de que as cadeias de L são cadeias de j símbolos x para 
qualquer j múltiplo de 3 (j/3 = n+r � j = 3(n+r), sendo n um número Natural 
maior do que zero e r um Inteiro diferente de zero). 
 Autômato Finito Exemplo 1 
 
 
Segunda, a de que as cadeias L são cadeias de j símbolos x para qualquer j 
múltiplo de 3 e maior do que 6 (j/3 = n+r � j = 3(n+r), sendo n,r números 
Naturais diferentes de zero). 
Autômato Finito Exemplo 
 
 
 
 
 
Gramática Regular 
Correspondente 
S � xA 
A � xB 
B � xC 
B � x 
C � xA 
Gramática Regular 
Correspondente 
S � xA 
A � xB 
B � xC 
C � xD 
D � xE 
E � xE 
E � x 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 8 
 
Alunos que apresentaram autômatos não equivalentes aos acima apresentados e que 
não mostraram como e por que tais autômatos correspondem a uma interpretação da 
equação que aparece no enunciado da questão não alcançaram pontuação. Alunos que 
construíram apenas o autômato ou apenas a gramática e justificaram por que ele ou 
ela atendem à restrição das cadeias expressa pela equação do enunciado obtiveram 
50% dos pontos da questão. 
 
8. [0,5 Pontos] Considere as seguintes linguagens: Lx = {} (uma linguagem vazia) e 
Ly = {ε} (uma linguagem que contém uma única cadeia, vazia) . Qual o conjunto 
“P” de produções α�β de cada uma delas? 
Px = {} 
Py = { S�ε } 
 
9. [1 Ponto] Desenhe os autômatos finitos que reconhecem a seguintes linguagens: 
 
Li = (a)* ∪ (ab) 
Lj = (a)* . (b)* -- o sinal ‘.’ marca a operação de concatenação 
Lk = Li ∪ Lj 
L = Li ∩ Lj 
 
Exemplos de autômatos que reconhecem Li 
 ou 
 
Exemplos de autômatos que reconhecem Lj 
 ou 
 
Autômato que reconhece Lk: é o mesmo de Lj, pois Li ⊂ Lj 
 
Autômato que reconhece L: é o mesmo de Li, pois Li ⊂ Lj 
 
 
10. [1,5 Pontos] Defina e explique o que é um autômato não determinístico, 
fornecendo especificamente: 
a. A definição em si; 
 
Um autômato não determinístico possui no seu conjunto de transições pelo 
menos duas tuplas (qi, σ, qj) e (qi, σ, qk) que possuem o mesmo estado de 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 9 
 
origem qi , mesmo símbolo de entrada σ e dois estados de destino diferentes qj 
e qk tais que qj ≠ qk. 
 
b. A especificação completa de um autômato AFND = {Estado_Inicial, 
Estados_Finais, Transições} que seja não determinístico, aceite a cadeia 
vazia εεεε e ilustre a definição apresentada em 10(a); 
 
Exemplo de solução: 
AFND = { q0, {q0,q1,q2}, { (q0,a,q1), (q0,a,q2), (q1,a,q1), (q2,b,q2) } } 
 
 
 
 
c. Uma gramática G = {V,Σ,S,P} equivalente à especificação do AFND 
apresentado em 10(b); e 
G = { V,Σ,S,P } onde 
Σ = { a, b } 
V = { S, A, B, a, b, ε } 
P = { S � aA, S � aB, S� ε, A� aA, A� ε, B� bB, B� ε } 
 
d. Um exemplo de como AFND aceita uma cadeia w com |w| ≥ 4, 
preenchendo uma tabela como ilustrada abaixo. 
 
Autômato AFND 
 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 <preencha> <preencha> avança para o 
próximo símbolo 
 
 
 
 
Autômato AFND 
Cadeia “abbb” 
Estado Corrente Símbolo Lido Estado Destino Movimento do 
Cursor 
q0 “a” (clone1) q1 
(clone2) q2 
avança para o 
próximo símbolo 
q1 
q2 
“b” (clone1) – FIM 
(clone2) q2 
(clone2) avança para 
o próximo símbolo 
-- 
q2 
“b” -- 
(clone2) q2 
(clone2) avança para 
o próximo símbolo 
-- 
q2 
“b” -- 
(clone2) q2 
(clone2) fim da 
entrada