PF - 2013.2 - Gabarito (Prof. Clarisse)

Prévia do material em texto

P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 1
 
Prova 4 de INF1626 – Linguagens Formais e Autômatos 
Guia de Respostas 
 
1. [1,5 pontos] Suponha que determinado sistema de automação industrial, por 
exemplo, seja comandado por instruções simples, emitidas através de um terminal 
de computador instalado em equipamentos de fábrica. As instruções seguem este 
padrão: 
 
Instrução = {'start', 'stop', 'redo'} ' P' {XYZ} 
 para X,Y,Z = qualquer algarismo de 0 a 9 
 
São exemplos de instruções válidas: 
 "start proc001" , "redo proc952" , "stop proc067" 
e são exemplos de instruções inválidas: 
 "startproc001" , "redo 952" , "stop Proc067" , 
 "start proc0671", "redo proc", "stop proc 067" 
 
a) A Gramática G, a seguir, é uma especificação correta do conjunto de instruções 
válidas para o sistema em questão? 
 
G = {V, , P, S} e V =   {S, A, B, C} 
 = {start, stop, redo, proc, ' ', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
 onde ' ' é um espaço em branco. 
P = { 
 S  AB 
 A  start | stop | redo 
 B  ' ' proc C C C 
 C  0| 1| 2| 3| 4| 5| 6| 7| 8| 9 
 } 
 
Sim, a gramática é uma especificação válida do conjunto de instruções. 
 
b) A linguagem acima especificada é estritamente livre de contexto? Por quê? 
 
Não, a gramática G não é estritamente livre de contexto. Primeiro, ela não 
tem nenhum padrão de cadeias com encaixe central recursivo (marca 
registrada das LLC’s) e segundo existe um autômato finito que reconhece 
todas e somente as instruções válidas do conjunto apresentado. Veja AF a 
seguir. 
 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 2
 
c) O Lema do Bombeamento para linguagens regulares se aplica à linguagem 
formada pelo conjundo de instruções em questão? Por quê? 
 
Não, o Lema do Bombeamento não se aplica à linguagem formada pelo 
conjunto de intruções em questão porque, seja na versão para linguagens 
regulares, seja na versão para linguagens livres de contexto, não é possível 
“bombear” (isto é, injetar) um número arbitrário de subcadeias em 
qualquer instrução válida de modo a que se obtenham outras instruções 
válidas. De fato, o conjunto de instruções é um conjunto finito (o que já 
seria uma violação da condição de bombeamento xy*z no lema tal como 
enunciado para Linguagens Regulares ou da condição de bombeamento 
xv*yu*z no lema tal como enunciado para Linguagens Livres de Contexto, 
cujo resultado em ambos os casos é um conjunto infinito de cadeias). 
Porém, a razão mais evidente de que o lema não se aplica é a única iteração 
de cadeias que temos, neste conjunto de instruções, é fixa e limitada a 
três repetições (CCC), o que é cabalmente diferente do que seria 
necessário para a aplicação do lema (C*). 
 
d) Existe um autômato finito que pode processar todas e somente as instruções 
válidas da linguagem em questão? Qual é ele? 
 
Sim, aparece na resposta à pergunta 1b, acima. 
 
e) Suponha que um aluno dedicado de LFA argumentasse que o conjunto de 
instruções do sistema mencionado nesta questão não constitui de fato uma linguagem 
formal e que deveríamos usar o termo 'linguagem', assim, entre aspas. Qual ou quais 
das respostas aos itens anteriores (de (a) a (d)) apresenta a justificativa mais forte que 
este aluno poderia estar usando para sustentar seu argumento? 
 
O argumento mais forte seria o apresentado em 1c, que mostra que o Lema 
do Bombeamento não se aplica ao conjunto de instruções. Assim, a 
caracterização de um conjunto finito de cardinalidade alta na forma de 
uma gramática ou linguagem é uma ‘conveniência’ prática. Mas há 
restrições formais importantes neste caso se comparado aos conjuntos 
infinitos que correspondem às linguagens de que trata a teoria de 
Linguagens Formais e Autômatos. 
 
2. [1,5 pontos] Máquinas de Mealy e Moore são transdutores finitos. Afirmamos, ao 
estudá-las, que “o tipo de linguagem gerada por um transdutor finito corresponde 
ao mesmo tipo da linguagem reconhecida pelo autômato subjacente (linguagens 
regulares)”. Explique, através de características formais das máquinas de Moore e 
Mealy, por que tal afirmativa é verdadeira. 
 
Um transdutor finito é uma extensão de um autômato finito. Além de ter 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 3
 
uma função de leitura/reconhecimento de cadeias simbólicas, ele tem 
também uma função de geração/gravação de cadeias simbólicas de saída, 
dependentes dos estados apenas (se for uma máquina de Moore) ou dos 
estados e transições (se for uma máquina de Mealy). 
 
A especificação formal de um transdutor finito é uma séptupla onde, além 
dos elementos que constituem a quíntupla que define um autômato finito 
(estado inicial, conjunto de estados finais, conjunto completo de estados, 
alfabeto da fita de entrada e uma função de transição de leitura da fita), 
há dois elementos adicionais: 
 alfabeto da fita de saída e 
 uma função de gravação de símbolos do alfabeto de saída definida 
para cada estado (nas máquinas de Moore) ou para cada transição 
entre estados (nas máquinas de Mealy). 
 
Se 
(i) a gravação de símbolos sucessivos de saída é determinada 
diretamente por um estado ou pela transição que levou até 
ele e 
(ii) tais estados e transições são os mesmos de um autômato 
finito, 
então 
 as cadeias gravadas na fita resultam do mesmo conjunto de estados 
e mesmas transições entre eles (a mesma estrutura de uma linguagem 
regular), sobre outro alfabeto, ou seja: outra linguagem regular. 
 
 
3. [3,5 pontos] Seja o autômato de pilha AP, abaixo caracterizado graficamente com 
o uso do JFLAP, e LAP a linguagem que ele reconhece. 
 
 
 
 
 
 
 
 
 
 
a) Complete, com uma expressão regular não estendida (isto é, que use somente 
união, interseção, concatenação e os operadores de fechamento transitivo e 
transitivo e recursivo), a regra gramatical que caracteriza as sentenças S da 
linguagem LAP: 
<S> ::= ______________________________________________________ 
 
AP = 
 
 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 4
 
<S> ::= a (ab)*b 
 
b) Escreva uma gramática livre de contexto na forma normal de Chomsky que 
especifique a mesma linguagem LAP especificada por AP. 
 
Gramática Não Normalizada 
ressaltando o Encaixe Central 
Recursivo 
 
Versão 1: S  ab | aSb 
 
Versão 2: S  AB | ASB 
 A  a 
 B  b 
Gramática Normalizada para FNC 
 
 
 
S  AB (normal na versão 2) 
A  a (normal na versão 2) 
B  b (normal na versão 2) 
S  AX (vem de SASB  SAX) 
X  SB (pois X substituiu SB acima) 
 
c) LAP é uma linguagem estritamente livre de contexto? Por quê? 
 
Sim, é. Ela não passa no Lema do Bombeamento das Linguagens Regulares 
(o que é suficiente para não ser regular) e, pelo próprio enunciado da 
questão, é aceita por um autômato de pilha. Além disto, como se vê nas 
respostas das questões anteriores, LAP tem encaixe central recursivo e 
caracteriza-se por cadeias com um número balanceado de a’s e b’s. 
 
d) Seja a Máquina de Turing MT, abaixo caracterizada graficamente com o uso do 
JFLAP. 
 
 
 
 
 
 
 
MT = 
 
Assinale se as afirmativas abaixo são falsas ou verdadeiras e justifique a sua 
resposta, considerando que estamos seguindo exatamente as mesmas convenções que 
o JFLAP para a especificação de transição de estados e consumo de cadeia de entrada 
e que AP aceita cadeias por pilha vazia ao passo que MT aceita cadeias por estado 
final. 
 
i. A cadeia ‘aabb’ é reconhecida por AP e MT. 
Verdadeira. 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 5
 
* A sequência de estados de AP para aceitar ‘aabb’ é: 
q0,q1 : lê entrada a, pop pilha Z, push pilha aZ 
q1,q1 : lê entrada a, pop pilha a,push pilha aa 
q1,q1 : lê entrada b, pop pilha a, push pilha  
q1,q1 : lê entrada b, pop pilha a, push pilha  
q1,q2 : lê entrada , pop pilha Z, push pilha  
q2: é estado final e não há mais símbolos a ler na fita de entrada 
* A sequência de estados de MT para aceitar ‘aabb’ é: 
q0,q1 : 
na fita de entrada: lê a, grava a, move cursor para a direita 
na fita auxiliar: lê , grava , não move cursor 
q1,q1 : 
na fita de entrada: lê a, grava a, move cursor para a direita 
na fita auxiliar: lê , grava a, move cursor para a direita 
q1,q1 : 
na fita de entrada: lê b, grava b, move cursor para a direita 
na fita auxiliar: lê , grava , move cursor para a esquerda 
q1,q2 : 
na fita de entrada: lê b, grava b, move cursor para a direita 
na fita auxiliar: lê a, grava , move cursor para a esquerda 
q2,q3 : 
na fita de entrada: lê , grava , não move cursor 
na fita auxiliar: lê a, grava , não move cursor 
q3: é estado final e não há mais símbolos a ler na fita de entrada 
 
ii. A cadeira ‘aaabb’ não é reconhecida nem por AP nem por MT. 
Verdadeira. 
* A sequência de estados de AP ao processar ‘aaabb’ é: 
q0,q1 : lê entrada a, pop pilha Z, push pilha aZ 
q1,q1 : lê entrada a, pop pilha a, push pilha aa 
q1,q1 : lê entrada a, pop pilha a, push pilha aa 
q1,q1 : lê entrada b, pop pilha a, push pilha  
q1,q1 : lê entrada b, pop pilha a, push pilha  
em q1 : lê entrada  e pilha aZ, o que impede que se faça uma transição 
O processamento para em estado não final e a cadeia é rejeitada. 
* A sequência de estados de MT ao processar ‘aaabb’ é: 
q0,q1 : 
na fita de entrada: lê a, grava a, move cursor para a direita 
na fita auxiliar: lê , grava , não move cursor 
q1,q1 : 
na fita de entrada: lê a, grava a, move cursor para a direita 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 6
 
na fita auxiliar: lê , grava a, move cursor para a direita 
q1,q1 : 
na fita de entrada: lê a, grava a, move cursor para a direita 
na fita auxiliar: lê , grava a, move cursor para a direita 
q1,q1 : 
na fita de entrada: lê b, grava b, move cursor para a direita 
na fita auxiliar: lê , grava , move cursor para a esquerda 
q1,q2 : 
na fita de entrada: lê b, grava b, move cursor para a direita 
na fita auxiliar: lê a, grava , move cursor para a esquerda 
em q2: 
na fita de entrada: lê , grava , não move cursor 
na fita auxiliar: lê a e não tem instruções sobre o que fazer, então para 
O processamento para em estado não final e a cadeia é rejeitada. 
 
iii. AP e MT reconhecem a mesma linguagem. 
Falsa. 
A cadeia ‘ab’ é reconhecida por AP mas não é reconhecida por MT. 
Além disto MT aceita cadeias anbm para n,m > 1 e m = n+1. 
 
iv. Quando AP atinge o estado final q2 a sua pilha pode não estar vazia. 
Falsa. 
Só existe a transição q1,q2 para q2, onde: lê-se vazio na fita (fim da 
entrada) , faz-se pop de Z na pilha (símbolo convencional de fundo) e 
grava-se  (i.e. apaga Z). Como nenhuma transição de AP empilha ZZ, 
quando o estado final q2 é atingido, a pilha está necessariamente vazia. 
 
v. Quando MT atinge o estado final q3 uma de suas fitas pode conter uma cadeia 
não nula de símbolos. 
Verdadeira. 
Nenhum símbolo da fita de entrada é apagado. Portanto, quando o estado 
final q3 é alcançado, a cadeia de entrada está integralmente preservada 
na fita de entrada. 
 
4. [2,5 pontos] Construa uma máquina de Turing MT’ de fita e cursor únicos que 
reconheça exatamente LAP, a linguagem reconhecida pelo autômato de pilha AP 
da questão anterior, e cujo critério de aceitação seja parada no estado final (a 
posição do cursor na fita não importa). 
 
 
Máquina de Exemplo de Resposta (usando um estado ‘trap’, q6): 
 
P4 de INF1626 – Turma 3WA / 11 de dezembro de 2013 de 09:05 às 10:55 horas p. 7
 
 
 
5. [1 ponto] Considere Σ = {a,b,c} e Li, i=1,2,3, as linguagens formadas por todas as 
cadeias passíveis de serem construídas sobre Σ, de tal forma que as seguintes regras 
sejam observadas respectivamente: 
 
(a) L1: as sentenças começam com a, terminam com dois c's consecutivos e 
apresentam um número par de símbolos b; 
 
(b) L2: as sentenças começam com b e apresentam um número total de símbolos que é 
ímpar; 
 
(c) L3: as sentenças apresentam qualquer quantidade de símbolos, mas não contêm 
dois (ou mais) símbolos c adjacentes. 
 
Construa expressões regulares que representem cada uma dessas linguagens. 
 
L1 = a ((a|c)* b (a|c)* b (a|c)* )* cc 
L2 = b ((a|b|c) (a|b|c))* 
L3 = ((a|b) c| (a|b))* 
 
* Questão retirada da lista de exercícios para a P2 
	PROVA 4 DE INF1626 - GUIA DE RESPOSTAS