P3 - 2013.2 - Gabarito (Prof. Clarisse)

Prévia do material em texto

P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 1 
 
Prova 3 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 30 minutos do tempo de realização. Nenhum 
aluno poderá começar a prova depois de o primeiro aluno entregar a dele e sair de sala. 
 
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! 
 
Parte I 
Questões de confirmação para avaliação do trabalho 
 
Estas questões estão formatadas em uma única tabela, na folha 2 desta prova. 
Queira prenchê-la a caneta. Não serão aceitas tabelas preenchidas a lápis. 
 
Suas respostas para as questões de confirmação totalizarão um fator F de 0 a 
1 que será multiplicado pela pontuação atribuída a cada parte do seu trabalho, 
já corrigido. F poderá assumir os seguintes valores, nas condições associadas: 
 
• F=1 para todo aluno que cujas respostas preenchidas na tabela sejam 
100% consistentes com o que verificamos ao corrigir o trabalho; 
 
• 0 
 
 ≤≤≤≤F<1 para todo aluno cujas respostas preenchidas na tabela acusem 
inconsistências com o que verificamos ao corrigir o trabalho (o valor 
de F será inversamente proporcional à extensão das inconsistências 
encontradas) 
 
• F=0 para todo aluno que não preencher a tabela, ou seja: respostas não 
preenchidas serão consideradas inconsistentes uma vez que as 
alternativas apresentadas cobrem todos os casos já verificados na 
correção. 
 
O trabalho vale 40% da prova, ou seja 4 pontos em 10. Sendo P a pontuação 
já atribuída por nossa correção ao trabalho entregue, a nota final do trabalho 
será calculada pela fórmula: Nota do Trabalho = F x P. 
 
A nota da prova será calculada pela seguinte fórmula: 
 
Nota da Prova = Nota do Trabalho [0..4] + Nota da Parte II [0..6] 
 
P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 2 
 
 
Preencha a tabela abaixo, marcando com um ‘x’ as opções que se aplicam ao trabalho 
que você entregou para compor a nota da P3. 
 
 Funciona para a Massa de Testes 1 
 
Funciona para a Massa de Testes 2 
1. Algoritmo de 
eliminação de 
símbolos 
inúteis 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
2. Algoritmo de 
eliminação de 
símbolos 
inacessíveis 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
3. Algoritmo de 
eliminação de 
produções em 
vazio 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
4. Algoritmo de 
eliminação de 
produções 
unitárias 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
5. Algoritmo de 
eliminação de 
recursões à 
esquerda 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
6. Algoritmo de 
normalização 
das produções 
pela FNG 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
( ) Sim. 
( ) Não sei; não testei. 
( ) A minha implementação deste 
algoritmo não está funcionando. 
( ) O meu trabalho não inclui nenhuma 
implementação para este 
algoritmo. 
 
Se você tem alguma observação a adicionar, escreva aqui: 
_____________________________________________________________________ 
_____________________________________________________________________ 
_____________________________________________________________________ 
_____________________________________________________________________ 
_____________________________________________________________________ 
 
P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 3 
 
Parte II 
Questões sobre a matéria da prova 
 
1. Sobre a linguagem L = anbncn para n>0 podemos afirmar que: (marque V ou F) 
[ 1 ponto] 
a. se trata de uma linguagem livre de contexto. ( ) V (X) F 
b. não se trata de uma linguagem livre de contexto porque não é possível 
aplicar a suas cadeias o Lema do Bombeamento para as linguagens livres de 
contexto. (X) V ( ) F 
c. seria uma lingagem livre de contexto se n ≥≥≥≥ 0, ou seja: o que impede a 
aplicação do Lema do Bombeamento a L é não ser possível operar uma 
retração nas cadeias em an e cn em torno de bn. ( ) V (X) F 
d. seria uma linguagem livre de contexto se a subcadeia bn fosse uma 
concatenação do sufixo de an com o prefixo de cn. ( ) V ou (X) F 
e. seria uma linguagem livre de contexto se as cadeias de L tivessem o padrão 
anbncm ou anbmcn ou ambncn para n,m>0. (X) V ou ( ) F 
 
2. Sejam as produções P de uma Gramática G, expressas convencionalmente abaixo 
através de cadeias de símbolos terminais e não terminais. 
[ 2 pontos] 
 
P = { 
 S � ID | IMD 
 I � n | nn | nnn 
 M � pnnn | pnnnM 
 D � vmm 
 } 
 
a. Utilizando a norma EBNF , escreva um conjunto de produções P’ que 
especifica a mesma linguagem que P, mas que contém, comparativamente, 
um número menor de produções. Como unidade de contagem para 
produções, você pode utilizar o número de não terminais. Assim, por 
exemplo, uma boa solução seria reduzir o número de produções à metade (de 
4 em P para 2 em P’), ou até mesmo reescrever toda a gramática em uma 
única linha de produção. 
 
Na EBNF, por convenção: os símbolos não terminais são representados através de literais 
maiúsculos, entre ‘<’ e ‘>’ (exemplo: <S>); o operador de reescrita é representado por ‘::=’ 
(exemplo: <S> ::= ...); e para efeitos de simplificação notacional são admitidas do ladodireito 
das produções, expressões regulares (exemplo: (a | b)* c+ (da+)*). 
 
 
P’ = { 
<S> ::= (n|nn|nnn) (pnnn)* (vmm) 
} 
 
b. Sendo G uma gramática livre de contexto, a linguagem LG por ela 
especificada pode ser reconhecida por qualquer tipo de autômato associado 
a linguagens menos restritas do que ela na Hierarquia de Chomsky. 
Especifique as transições de estado de uma Máquina de Turing MT 
 
P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 4 
 
(determinística ou não, de fita limitada ou ilimitada, a seu critério) que 
reconheça LG. Note que você não precisa apresentar a especificação 
completa de MT; basta apresentar o conjunto completo de transições que 
ela deve efetuar para reconhecer LG sobre o alfabeto Σ = {n, m, p, v}. 
 
S = { (qi,<) → (q0,<,D) ; (q0,n) → (q1,n,D) ; (q1,n) → (q2,n,D) ; (q1,p) → (q4,p,D) ; 
(q1,v) → (q8,v,D) ; (q2,n) → (q3,n,D) ; (q2,p) → (q4,p,D) ; (q2,v) → (q8, v,D) ; (q3,p) 
→ (q4,p,D) ; (q3,v) → (q8,v,D) ; (q4,n) → (q5,n,D) ; (q5,n) → (q6,n,D) ; (q6,n) → 
(q7,n,D) ; (q7,p) → (q4,p,D) ; (q7,v) → (q8,v,D) ; (q8,m) → (q9,m,D) ; (q9,n) → 
(q10,m,D) } 
 
Máquina de Turing determinística e de fita limitada, com estado inicial qi, estado final 
q10, marcador de início de fita <. 
 
c. Dadas as características de gravação e movientação de cabeçote de MT, 
você tem argumentos para afirmar que LG não é uma linguagem 
estritamente livre de contexto? Justifique sua resposta. 
 
Como o cabeçote da MT apresentada simplesmente lê cada terminal da cadeia de 
entrada, sem ter que gravar quaisquer informações de apoio ao processamento, para 
então o controlador fazer uma transição determinística entre estados, pode-se ver 
claramente que a máquina opera como um autômato finito determinístico. A 
linguagem em questão, portanto, não é estritamente livre de contexto, pois é uma 
linguagem regular. 
 
3. Em um processo de simplificação de gramáticas livres de contexto, a aplicação do 
algoritmo de eliminação dos símbolos inúteis influencia o resultado do algoritmo 
de eliminação de símbolos inacessíveis ? E o contrário, pode-se afirmar ? 
Justifique a sua resposta. 
[ 0,5 pontos] 
 
A ordem de aplicação não importa. Podemos ter: 
 1. símbolos úteis e acessíveis 
 2. símbolos úteis e inacessíveis 
 3. símbolos inúteis e acesssíveis 
 4. símbolos inúteis e inacessíveis 
Queremos tratar os casos 2, 3 e 4. O caso 4 trivialmente não depende da ordem, pois 
seriam eliminados por ambos os algoritmos. 
Agora, pode-se observar que os casos 2 e 3 representam partições disjuntas do 
conjunto de não-terminais. Deste modo, a aplicação de cada algoritmo eliminaria 
apenas os membros de seu respectivo conjunto (e produções de outros não-terminais 
que usassem tais membros). Assim, a ordem não importa. 
 
4. Considere o seguinte algoritmo de eliminação de produções em vazio (Ramos, 
2009), cuja implementação era parte do trabalho proposto para a sua turma. 
[ 2 pontos] 
 
Entrada: uma gramática livre de contexto G=(V=N∪Σ, Σ, P, S). 
Saída: uma gramática livre de contexto G′=(V′=N′∪Σ, Σ, P′, S′), tal que L(G′) = L(G) e: 
 i) Se ε ∉ L(G), então não há produções em vazio em G', ou 
 
P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 5 
 
 ii) Se ε ∈ L(G), então a única produção em vazio em G' é S' → ε, onde S' é 
 a raiz de G' e S' não aparece no lado direito de nenhuma produção. 
 
Método: 
1. E0 ← {A | A → ε ∈ P}; 
2. i ← 1; 
3. Ei ← Ei-1 ∪ {A | A → X1X2...Xn ∈ P e X1,X2...Xn ∈ Ei−1}; 
4. Se Ei ≠ Ei−1, então: 
 a) i ← i + 1; 
 b) Desviar para (3); 
Caso contrário: 
 a) E ← Ei-1; 
5. P' ← ∅; 
6. P' ← { A → β ∈ P | β ≠ ε }; 
7. Considerem-se as produções de P' no formato: 
 A → α0B1α1B2α2...Bkαk, com αi ∈ (V-E)
+
 e Bi ∈ E 
A versão final do conjunto P' é obtida acrescentando-se à sua versão anterior o conjunto das 
produções obtidas pela substituição dos símbolos Bi, 0 ≤ i ≤ k por ε, considerando-se todas as 
combinações possíveis, sem no entanto gerar a produção A → ε. 
8. Se S ∈ E, então: 
 a) P' ← P' ∪ {S' → S | ε}; 
 b) N' ← N ∪ {S'}; 
 Caso contrário: 
 a) N' ← N; 
 b) S' ← S. 
 
Aplique este algoritmo à gramática livre de contexto G, abaixo, e apresente as 
produções da gramática G’ que resulta desta simplificação (não é preciso mostrar os 
passos do algoritmo, mas as produções resultantes têm de espelhar exatamente o 
resultado da sua aplicação). 
 
G = 
S → aAbBcC 
A → aA | ε 
B → bB | aA | ε 
C → aA | ε | bB 
 
G’ = 
S → aAbBcC | abBcC | aAbcC | aAbBc | aAbc | abBc | abcC | abc 
A → a | aA 
B → b | bB | a | aA 
C → a | aA | b | bB 
 
 
P3 de INF1626 – Turma 3WA / 4 de dezembro de 2013 de 09:05 às 10:55 horas p. 6 
 
 
5. Qual a ordem máxima (pior caso) da complexidade de espaço das Máquinas de 
Turing de Fita Limitada em relação ao tamanho da entrada que processam: 
constante, linear ou quadrática? Justifique a sua resposta. 
[ 0,5 pontos] 
 
Como a máquina de Turing é de fita limitada (ou seja, pode-se escrever apenas nos 
espaços ocupados pela cadeia de entrada), usam-se, no pior caso, todos os n espaços 
da cadeia de entrada para armazenamento de informações de amparo ao 
processamento da cadeia. Assim, temos uma complexidade de espaço que, no pior 
caso, é n. Portanto, é linear.