P2 - 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 2 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.5 Pontos] Conceituação 
 
Apresente definições corretas e precisas para os seguintes conceitos: 
 
a. Gramática Regular à Esquerda 
A pergunta é sobre uma GRAMÁTICA regular à esquerda, 
não sobre um Autômato Finito ou Reconhecedor 
equivalente ou sobre as Linguagens que elas descrevem. 
O fato de as estruturas sintáticas da linguagem 
descrita por este tipo de gramática “crescerem para a 
esquerda” é sua principal característica e não está 
errado mencionar o fato na resposta. Entretanto, esta 
menção não é uma definição (e é, aliás, dispensável na 
definição). 
 
Exemplo de Resposta Correta: 
Uma gramática regular à esquerda G é definida por uma quádrupla 
G=<V, , P, S> , onde: 
 V é o vocabulário (símbolos terminais e não terminais) 
  é o alfabeto de símbolos terminais e S é o símbolo raiz 
P é o conjunto de produções (regras) do tipo    , onde   (V-) e ||=1, 
  (V-)  {},     {} . 
 
Para obter 100% dos pontos, a definição apresentada 
tem de incluir todas as características acima, 
enunciadas em termos dos seguintes elementos 
formais: vocabulário, alfabeto, produções e 
restrições sobre elas. 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 2
 
b. Autômato Mínimo 
 
Exemplo de Resposta Correta: 
Autômato mínimo é o autômato finito determinístico com o menor número de 
estados possível capaz de reconhecer uma determinada linguagem regular L, 
sendo que ele é único. 
 
Algumas das respostas apresentadas definiam autômatos 
“menores que outros”, mas não necessariamente mínimos. 
Outras não faziam referência à linguagem que o conjunto 
de autômatos comparados (mínimos e não mínimos) têm de 
reconhecer, a mesma. Finalmente, algumas respostas eram 
quase mera paráfrase da pergunta: “autômato mínimo é 
aquele que tem o mínimo de estados possíveis.” Todos os 
casos citados levaram a descontos (maiores ou menores) 
na pontuação deste item da questão. 
 
c. Transdutor Finito 
 
Exemplo de Resposta Correta: 
Transdutor finito é uma extensão de autômatos finitos determinísticos que se 
caracterizam pela escrita de símbolos numa fita de saída, além da leitura de 
símbolos da fita de entrada. Portanto, os transdutores lêem símbolos do alfabeto 
de entrada  e escrevem símbolos do alfabeto de saída . A escrita de símbolos 
pode ser baseada nos estados percorridos durante a execução do autômato, ou nas 
transições efetuadas durante essa transição. 
 
Várias respostas mencionavam parte das características 
definitórias dos transdutores, mas não todas elas. Além 
disto, houve casos de definições circulares (por 
exemplo: “são transdutores que ...” ou “autômatos em 
que as transduções ...”). 
 
2. [2.5 Pontos] Conversão de Gramática para Autômato e 
Minimização de Autômatos 
 
Seja a seguinte gramática regular à direita: 
 
S  aS 
S  aX 
X  b 
X  bS 
X  bC 
C  c 
C  cC 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 3
 
a) Especifique um Autômato Finito Determinístico que reconheça exatamente a 
mesma linguagem que a gramática acima especifica. 
 
Exemplo de Resposta Correta: 
Inicialmente, criamos o autômato não determinístico a partir da gramática: 
 
 
Quem preferiu trabalhar com a expressão regular 
equivalente, ela é: 
a+ (b a+)* b c* ou, de forma mais simples, (a+ b)+ c*. 
 
Em seguida, é necessário eliminar as transições não determinísticas: 
Q = {q0,q1,q2,q3} 
F = {q3} 
: 
q0,a,[q0 q1] 
q1,b,[q0 q2 q3] 
q2,c,[q2 q3] 
 
Criando um novo estado qn1=[q0 q1]: 
Q = {q0,q1,q2,q3,qn1} 
F = {q3} 
: 
q0,a,qn1 
q1,b,[q0 q2 q3] 
q2,c,[q2 q3] 
qn1,a,[q0 q1] (qn1) 
qn1,b,[q0 q2 q3] 
 
Criando um novo estado qn2=[q0 q2 q3]: 
Q = {q0,q1,q2,q3,qn1,qn2} 
F = {q3,qn2} 
: 
q0,a,qn1 
q1,b,qn2 
q2,c,[q2 q3] 
qn1,a,qn1 
qn1,b,qn2 
qn2,a,[q0 q1] (qn1) 
qn2,c,[q2 q3] 
 
Criando um novo estado qn3=[q2 q3]: 
Q = {q0,q1,q2,q3,qn1,qn2,qn3} 
F = {q3,qn2,qn3} 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 4
 
: 
q0,a,qn1 
q1,b,qn2 
q2,c,qn3 
qn1,a,qn1 
qn1,b,qn2 
qn2,a,qn1 
qn2,c,qn3 
qn3,c,qn3 
 
Podemos eliminar os estados q1, q2 e q3, pois são inacessíveis (q0 transita para qn1, e 
a partir dele temos apenas transições entre estados novos). 
 
Assim, o autômato final seria: 
Q = {q0,qn1,qn2,qn3} 
F = {qn2,qn3} 
: 
q0,a,qn1 
qn1,a,qn1 
qn1,b,qn2 
qn2,a,qn1 
qn2,c,qn3 
qn3,c,qn3 
 
 
 
 
b) Demonstre que o autômato que você especificou é (ou não é) o autômato 
mínimo capaz de reconhecer a linguagem em questão. 
 
 
Exemplo de Resposta Correta: 
Adicionando o "trap state": 
 
 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 5
 
Estados não-finais Estados finais 
(0,1,T) (2,3) 
Expandindo com (b): 
(0,T) (1) (2,3) 
Expandindo com (a): 
(0)(T) (1) (2)(3) 
 
Como todos os estados são distinguíveis, o autômato já era mínimo. 
 
 
3. [1.5 Pontos] Lema do Bombeamento 
 
A linguagem L = {ww | w  {0,1}*} é regular? Mostre por quê. 
 
 
Exemplo de Resposta Correta: 
A linguagem L é formada por todas as cadeias de 0's e 1's (possivelmente vazia) que 
consistem na concatenação de duas subcadeias idênticas. 
 
Supondo que L seja regular, então existe um autômato finito com n estados que a 
reconhece. 
 
Para verificar a validade do lema do bombeamento, iremos considerar a cadeia 
w = 0n1n0n1n , que satisfaz uma das condições do lema (wL e |w| >= n). Bastaria 
mostrar que não há nenhuma partição possível de w que respeite todas as condições 
do lema. Vamos então argumentar que, para todas as maneiras de dividir w em três 
partes xyz (onde |xy|  n e |y|  1), existe pelo menos um valor para i  0 que de modo 
que xyiz  L. 
 
Para a cadeia w escolhida, a subcadeia xy é necessariamente composta apenas de 0's 
já que devemos observar a condição |xy|  n e sabemos que w=0n1n0n1n. Qualquer 
partição incluindo ‘1’ extrapola o limite da condição. Portanto, para |xy|  n, a 
subcadeia y só pode ser composta de um ou mais 0's. Ao "bombear" essa subcadeia 
com qualquer valor de i1, a primeira metade da cadeia w ficará diferente da (ou 
“desbalanceada” em relação à) segunda metade, o que implica que a nova cadeia 
gerada não irá pertencer à linguagem. Portanto, o lema do bombeamento não se 
aplica, e podemos concluir que L não é regular. 
 
A pista clara de que L não é regular está no 
balanceamento das cadeias que a ela pertencem (formadas 
pela exata repetição de uma subcadeia de módulo igual à 
metade do módulo da cadeia completa). Este exemplo de 
linguagem não regular foi repetidas vezes mencionado em 
sala ou em exercícios. A maior fonte de erros da questão 
(menor índice de pontuação da prova) foi a interpretação 
incorreta da expressão “L=ww”. A maioria nãopercebeu que 
se trata de uma cadeia simétrica (duas cadeias w 
repetidas). 
 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 6
 
4. [1,5 Pontos] Conversão de Autômato Finito para Gramática 
Regular e Expressão Regular 
 
Seja o seguinte Autômato Finito AF: 
 
 
a) Escreva uma Gramática Regular à Direita que expresse exatamente a mesma 
linguagem que AF reconhece. 
 
 
Exemplo de Resposta Correta: 
S  0A 
A  0B 
B  0B 
B  1C 
C  0B 
C  1D 
D  0B 
D  1D 
D   
 
b) Escreva uma Expressão Regular que represente o padrão de cadeias 
pertencentes a esta linguagem. 
 
 
Exemplo de Respostas Corretas Conferidas no JFLAP: 
 
000*1(00*1)*1(1|00*1(00*1)*1)* 
00(0|10|111*0)*111* 
000*1(0*1)*1(00*1(0*1)*1)* 
 
Algumas respostas para a expressão regular foram 
extremamente elegantes. Houve no entanto um número 
surpreendentes de respostas erradas para a GLR à 
direita, onde não aparecia regra com terminais apenas 
(para “terminar” a derivação). 
 
5. [1,5 Pontos] Minimização de Autômatos 
 
Seja o Autômato Finito AF: 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 7
 
 
 
Mostre que/se ele pode ser minimizado para um autômato AFmin, capaz de reconhecer 
exatamente a mesma linguagem que ele. (Se sua resposta for positiva, construa 
AFmin.) 
 
Adicionando o "trap state": 
 
 
 
Verificando os estados distinguíveis: 
Não finais Finais 
(0,1,2,3,4,5,T) (2,6) 
Expandindo com 'b': 
(0,3,4,T) (1,5) (2,6) 
Expandindo com 'a': 
(0,3,4) (T) (1,5) (2,6) 
Expandindo com 'a': 
(0,3,4) (T) (1) (5) (2,6) 
 
Como não é possível fazer mais distinções entre os grupos, os novos estados para o 
autômato mínimo são: 
q0 (0,3,4) 
q1 (1) 
q2 (5) 
q3 (2,6) 
 
A maioria das respostas, surpreendentemente (face a outra 
questão que já envolvia conhecimento de minimização de 
autômatos) apresentou autômatos que não correspondem ao 
original (não mínimo). Não distinguiram q1 e q5 
 
P1 de INF1626 – Turma 3WA / 4 de setembro de 2013 de 09:05 às 10:55 horas p. 8
 
(distintos para ‘a’ depois de separarmos o ‘trap’). Como 
resultado, aceitaram subcadeias (aa)+ depois de um ‘b’(o 
que não é autorizado pelo autômato original). 
 
 
 
6. [1,5 Pontos] Conversão LR para LL 
 
Qual o procedimento de conversão de uma linguagem linear à direita para uma 
linguagem linear à asquerda? Ilustre a sua resposta utilizando uma linguagem regular 
de sua escolha. 
 
O procedimento consiste em encontrar a gramática regular à direita (GRD) que gera a 
linguagem reversa (Lrev), pois a partir dela podemos transformar as suas regras para 
convertê-la na GRE que gera L, da seguinte forma: 
 para cada regra    , com    e   (V-), crie uma regra '  ' 
 para cada regra    , com   (V  {}), crie uma regra '   
 
 
Por exemplo, seja a GRD abaixo para a linguagem L = a+b+ : 
S  aS 
S  B 
B  bB 
B  b 
 
Nesse caso, Lrev = b+a+ . Uma possível GRD para gerar Lrev seria: 
S  bS 
S  A 
A  aA 
A  a 
 
Ao transformar essa GRD em GRE, obtemos uma gramática que gera (Lrev)rev = L: 
S'  S'b 
S'  A' 
A'  A'a 
A'  a 
 
Esta foi a questão mais fácil da prova. A maioria das 
respostas às quais não foi dada pontuação cheia da 
questão tinha problemas na apresentação do algoritmo ou 
procedimento de conversão. A correção tolerou algumas 
imprecisões ou variações em relação ao algoritmo acima 
**se** a ilustração estivesse correta.