Download - LFA Aula06 Exercicios
-
5/27/2018 LFA Aula06 Exercicios
1/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 1
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Linguagens Formais e Autmatos (LFA)Linguagens Formais e Autmatos (LFA)
Aula de 28/08/2013Aula de 28/08/2013
Sobre as respostas das duplas aosSobre as respostas das duplas aosexercexerccios propostoscios propostos
Clarisse S. de Souza, 2013 1
-
5/27/2018 LFA Aula06 Exercicios
2/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 2
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Fatos extrados dos scores das duplas
Tempo mdio de resposta- A srie inteira de exerccio,conforme informado pelas
duplas, foi resolvida em 31:28minutos em mdia.
- O percentual mdio de
confiana das duplas nasrespostas dadas (opocompleto e correto) foi de62%,
H duplas com menos de 30% degrau de certeza sobre seudesempenho: sinal no muito
promissor de acmulo de dvidassobre a matria.------------------------------------Sobre se as duplas que tm alto
grau de certeza a respeito deseu desempenho esto de fatosabendo tudo ou no, vamosconferir nos prximos slides.
-
5/27/2018 LFA Aula06 Exercicios
3/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 3
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccio 1
Seja o autmato A =1. Utilizando o seguinte formalismo simplificado:
A : Q = I = F = = = tuplas de transio (qi,, qj) onde
qi = estado corrente
= smbolo lido pelo cabeoteqj = estado-alvo da transio
defina formalmente o autmato A.
-
5/27/2018 LFA Aula06 Exercicios
4/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 4
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Resposta do Exerccio 1
A : {Q = {q0, q1, q2}I = {q0}F = {q1} = {a,b} = {
(q0,a,q0), (q0,b,q1),
(q1,b,q2), (q2,b,q1)}}
-
5/27/2018 LFA Aula06 Exercicios
5/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 5
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccio 2 - Resposta
Seja o autmato A =
2. Que tipos de cadeias este autmato aceita?a*b(bb)*
Ou seja, qualquer cadeias que resulte da concatenao de:
Zero ou mais a com Um b com Zero ou mais bb (isto , a cadeia formada pela concatenao de
b com b, iterada (=repetida) zero ou mais vezes)
-
5/27/2018 LFA Aula06 Exercicios
6/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 6
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Comentrio sobre a resposta do exerccio 2
Algumas duplas responderam algo assim:Cadei as f or madas por zer o a i nf i ni t os a segui dosde 1 a i nf i ni t os b, sendo que o nmer o de b
t em de ser mpar .
verdade. Este o tipo de cadeia formada. Mas, como estamosaprendendo a formalizar linguagens, a resposta destas duplas ainda informal (embora no esteja errada). Para dar umaresposta formal e correta, vamos utilizar os conceitos e as
operaes aprendidas na Aula 3 (slides de 8 em diante,sobretudo). o que veem na resposta apresentada no slideanterior: a*b(bb)* .
-
5/27/2018 LFA Aula06 Exercicios
7/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 7
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccio
Seja o autmato A =3. Utilizando tuplas (qi,,qj) para representar (estado corrente,
smbolo lido, prximo estado), apresente a sequncia completade reconhecimento para as seguintes cadeias: ab (q0,a,q0),(q0,b,q1) aaaaab (q0,a,q0), (q0,a,q0), (q0,a,q0), (q0,a,q0), (q0,a,q0),(q0,b,q1) abbbbb (q0,aq0),(q0,b,q1),(q1,b,q2),(q2,b,q1), (q1,b,q2),(q2,b,q1) b (q0,b,q1)
a (q0,a,q0) -- Esta cadeia no aceita: por qu? bb (q0,b,q1),(q1,b,q2) -- Esta cadeia no aceita: por qu?
-
5/27/2018 LFA Aula06 Exercicios
8/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 8
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccio
Seja o autmato A =
4. Utilizando os programas em Ruby apresentados na aula passada,implemente o reconhecedor associado a A.
Basta que editem um dos arquivos Exemplo*.rb do diretrio afd.Vejam no slide seguinte o resultado no ambiente instalado nocomputador de um dos professores da disciplina.
-
5/27/2018 LFA Aula06 Exercicios
9/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 9
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
-
5/27/2018 LFA Aula06 Exercicios
10/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 10
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccio
Seja o autmato A =5. Escreva uma gramtica regular que gere exatamente as mesmascadeias aceitas pelo reconhecedor que voc implementou.Lembrete - Uma gramtica regular definida por uma tupla {V,,P,S} onde: V=vocabulrio
finito e no vazio com TODOS os smbolos que aparecem esquerda ou direita de
regras de reescrita;
o alfabeto da linguagem (isto , os smbolos terminais quepodem aparecer em cadeias gramaticais da linguagem); P o conjunto de regras dereescrita; e S o smbolo raiz de todas as derivaes.
GramReg : V = {a,b,A,B,C,D,S} ; = {a,b} ; S;
P = { S
b A
bCS bC C bDS aA D bA aA D bC
A b }
-
5/27/2018 LFA Aula06 Exercicios
11/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 11
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Como conferir se uma gramtica proposta est certa?
JFLAP1. Clique em Grammar2. Na janela nova, transcreva a
sua gramtica candidata
3. Teste se a sua gramtica regular (menu Test)4. Se for, a mensagem diz
entre parnteses
(Regular Grammar andContext Free Grammar);prossiga.
[Continua no prximo slide]
-
5/27/2018 LFA Aula06 Exercicios
12/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 12
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Como conferir se uma gramtica proposta est certa?
[Continuao]5. Crie uma massa de testes, comcadeias que voc sabe que devem ser
aceitas e que devem ser rejeitadas.6. Verifique o que acontece quando sua
massa de testes processada: Clique em Input e selecione
Multiple CYK Parse Quando a nova janela abrir, fornea
sua massa de teste e Clique em Run InputsSe sua gramtica for equivalente ao
reconhecedor associado ao autmatoA, ento ela dever:
-- gerar corretamente (e fazer umparse bem sucedido) de cadeiasa*b(bb)* [accept]
-- no gerar cadeias cuja forma no sejaw = a*b(bb)*
Para testar a cadeia vazia, cliquem em Enterlambda.
-
5/27/2018 LFA Aula06 Exercicios
13/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 13
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Resultado da Gramtica Proposta
Este oexerccio maisdifcil da srie. s para testar
as intuies devocs.Estudaremosalgoritmos de
converso entre
Gramticas eAutmatos noprximo captulo
da matria.
-
5/27/2018 LFA Aula06 Exercicios
14/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 14
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccios
Sejam as gramticas G1, G2, G3, G4 e G5, cujas regras de reescritaso as seguintes:
1. Diga que tipo de gramtica cada uma delas, segundo aHierarquia de Chomsky.
G1
S -> a
S -> aS
G2
S -> AS
bS ->SbA -> aA -> bA -> aA
G3
S -> AS
S -> bA -> aA -> aA
G4
S -> ASB
S -> cA -> aA -> aAB -> bB -> bB
G5
S -> XC
X -> xX -> xXxxxX -> xxXxxxC -> xxC -> C
RegularTipo 3
Sensvel aContextoTipo 1
Livre deContextoTipo 2 Livre deContexto
Tipo 2IrrestritaTipo 0
-
5/27/2018 LFA Aula06 Exercicios
15/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 15
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exerccios
Sejam as gramticas G1, G2, G3, G4 e G5, cujas regras de reescrita so asseguintes:
2. Mostre o caminho de derivao de pelos menos duas cadeias diferentespara cada uma delas, usando a notao do slide 5.
G1
S -> a
S -> aS
G2
S -> AS
bS ->SbA -> aA -> bA -> aA
G3
S -> AS
S -> bA -> aA -> aA
G4
S -> ASB
S -> cA -> aA -> aAB -> bB -> bB
G5
S -> XC
X -> xX -> xXxxxX -> xxXxxxC -> xxC -> C
-
5/27/2018 LFA Aula06 Exercicios
16/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 16
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exemplos de Derivaes
Para G1: S -> a S -> aS -> aaS -> aaa
Para G2: S -> AS -> aS -> aAS -> abS -> aSb -> aASb -> aaSb -> Temos um problema com esta gramtica; o processo de
derivao no para. Podem tentar vrios caminhosalternativos, todos levaro a pontos da derivao - aS oubS-> Sb - que j foram visitados e de onde no se
consegue sair. um ciclo pernicioso que mostra que estagramtica est mal-formada.
Mais adiante na matria procuraremos caracterizarformalmente o sinal da m-formao desta gramtica.
G1
S -> aS -> aS
G2
S -> ASbS ->SbA -> aA -> bA -> aA
-
5/27/2018 LFA Aula06 Exercicios
17/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 17
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Exemplos de Derivaes
Para G3: S -> AS -> aAS -> aaAS -> aaaS -> aaab S -> AS -> aAS -> aaAS -> aaaS -> aaaAS -> aaaaS -> aaaab
Para G4: S -> ASB -> aASB -> aaSB -> aacB -> aacbB -> aacbbB -> aacbbbB ->aacbbbb S -> ASB -> aASB -> aaASB -> aaaASB -> aaaaSB -> aaaacB ->
aaaacbB -> aaaacbbB -> aaaacbbbB -> aaaacbbbb
G3
S -> ASS -> bA -> aA -> aA
G4
S -> ASB
S -> cA -> aA -> aAB -> bB -> bB
-
5/27/2018 LFA Aula06 Exercicios
18/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 18
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Algumas Derivaes para G5
S -> XC -> xC -- parou a derivao aqui!S -> XC -> xXC -> xxC -> S -> XC -> xXC -> xxC -> C -- parou a derivao aqui!
S -> XC -> xXC -> xxXC -> xxxC -> xS -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxxC -> xxS -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxXxC
-> xxXxxC -> xxX (Ufa!) -> xxxxxxxxxxxxx
S -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxXxC-> xxXxxC -> xxXC(Oh, no!)
G5
S -> XCX -> xX -> xXxxxX -> xxXxxxC -> xxC -> C
-
5/27/2018 LFA Aula06 Exercicios
19/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 19
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Explorando o JFLAP na derivao gramatical
Veja o vdeo de demonstrao online.
Video S-aS.mp4
Video S-aS-derivacao.mp4
-
5/27/2018 LFA Aula06 Exercicios
20/20
Informtica
PUC-Rio
Clarisse S. de Souza, 2013 20
INF1626 Linguagens Formais e Autmatos (2013INF1626 Linguagens Formais e Autmatos (2013--2)2)
Mltiplos caminhos de derivao
O importante que a cada passo seja vlida da reescrita realizada, isto : que haja uma regra
autorizando a substituio. Diferentes caminhos tm, computacionalmente, diferentesvantagens e desvantagens, dependendo do propsito e do contexto da derivao.
Video S-aS-parsers.mp4
Vejam como amesma cadeia
aceita por 3parsers
(analisadoressintticos)
diferentes, que
geram 3 rvoresdiferentes!