Linguagens Formais e Autômatos (LFA)inf1626/docs/2013/extras/LFA-aula06-exercicios.pdf · qj = estado-alvo da transição defina formalmente o autômato A. Informática PUC-Rio ©Clarisse

InformáticaPUC-Rio

©Clarisse S. de Souza, 2013 1

INF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)

Linguagens Formais e Autômatos (LFA)Linguagens Formais e Autômatos (LFA)

Aula de 28/08/2013Aula de 28/08/2013

Sobre as respostas das duplas aosSobre as respostas das duplas aosexercexercíícios propostoscios propostos


InformáticaPUC-Rio



Fatos extraídos dos scores das duplas

Tempo médio de resposta- A série inteira de exercício, conforme informado pelas duplas, foi resolvida em 31:28 minutos em média.

- O percentual médio de confiança das duplas nas respostas dadas (opção “completo e correto”) foi de 62%,

Há duplas com menos de 30% de grau de certeza sobre seu desempenho: sinal não muito promissor de acúmulo de dúvidas sobre a matéria.------------------------------------Sobre se as duplas que têm alto grau de certeza a respeito de seu desempenho estão de fato sabendo tudo ou não, vamos conferir nos próximos slides.

InformáticaPUC-Rio



Exercício 1Seja o autômato A =

1. Utilizando o seguinte formalismo simplificado:A : Q = <conjunto completo de estados>

I = <conjunto unitário de estados iniciais>F = <conjunto completo de estados finais> = <alfabeto reconhecido> = tuplas de transição (qi,, qj) onde

qi = estado corrente = símbolo lido pelo cabeçote

qj = estado-alvo da transição

defina formalmente o autômato A.

InformáticaPUC-Rio



Resposta do Exercício 1

A : {Q = {q0, q1, q2}I = {q0}F = {q1} = {a,b} = {

(q0,a,q0), (q0,b,q1),(q1,b,q2), (q2,b,q1)

}}

InformáticaPUC-Rio



Exercício 2 - Resposta

Seja o autômato A =

2. Que tipos de cadeias este autômato aceita?a*b(bb)*

Ou seja, qualquer cadeias que resulte da concatenação de:– Zero ou mais “a” com– Um b com– Zero ou mais “bb” (isto é, a cadeia formada pela concatenação de

“b” com “b”, iterada (=repetida) zero ou mais vezes)

InformáticaPUC-Rio



Comentário sobre a resposta do exercício 2

Algumas duplas responderam algo assim:Cadeias formadas por zero a infinitos “a” seguidos

de 1 a infinitos “b”, sendo que o número de “b”tem de ser ímpar.

É verdade. Este é o tipo de cadeia formada. Mas, como estamos aprendendo a “formalizar” linguagens, a resposta destas duplas éainda “informal” (embora não esteja errada). Para dar uma resposta formal e correta, vamos utilizar os conceitos e as operações aprendidas na Aula 3 (slides de 8 em diante, sobretudo). É o que veem na resposta apresentada no slide anterior: a*b(bb)* .

InformáticaPUC-Rio



ExercícioSeja o autômato A =

3. Utilizando tuplas (qi,,qj) para representar (estado corrente, símbolo lido, próximo estado), apresente a sequência completa de 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 não é aceita: por quê?• bb (q0,b,q1),(q1,b,q2) -- Esta cadeia não é aceita: por quê?

InformáticaPUC-Rio



ExercícioSeja o autômato 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 diretório afd.Vejam no slide seguinte o resultado no ambiente instalado no computador de um dos professores da disciplina.

InformáticaPUC-Rio



InformáticaPUC-Rio



Exercício

Seja o autômato A =5. Escreva uma gramática regular que gere exatamente as mesmas

cadeias aceitas pelo reconhecedor que você implementou.Lembrete - Uma gramática regular é definida por uma tupla {V,,P,S} onde: V=vocabulário

finito e não vazio com TODOS os símbolos que aparecem à esquerda ou direita de regras de reescrita; é o alfabeto da linguagem (isto é, os símbolos terminais que podem aparecer em cadeias “gramaticais” da linguagem); P é o conjunto de regras de reescrita; e S é o símbolo raiz de todas as derivações.

GramReg : V = {a,b,A,B,C,D,S} ; = {a,b} ; S;P = { S b A bC

S bC C bDS aA D bA aA D bC A b }

Clarisse

Cross-Out

Este símbolo não existe (é desnecessário, confiram!). Ficou no slide por erro de edição. Queiram desculpar.

InformáticaPUC-Rio



Como conferir se uma gramática proposta está certa?

JFLAP1. Clique em “Grammar”2. Na janela nova, transcreva a

sua gramática candidata3. Teste se a sua gramática é

regular (menu “Test”)4. Se for, a mensagem diz

entre parênteses“(Regular Grammar andContext Free Grammar)”; prossiga.

[Continua no próximo slide]

InformáticaPUC-Rio



Como conferir se uma gramática proposta está certa?

[Continuação]5. Crie uma “massa de testes”, com

cadeias 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, forneça

sua “massa de teste” e• Clique em “Run Inputs”Se sua gramática for equivalente ao

reconhecedor associado ao autômato A, então ela deverá:

-- gerar corretamente (e fazer um “parse” bem sucedido) de cadeias a*b(bb)* [accept]

-- não gerar cadeias cuja forma não seja w = a*b(bb)*

Para testar a cadeia vazia, cliquem em “Enter lambda”.

InformáticaPUC-Rio



Resultado da Gramática Proposta

Este é o exercício mais difícil da série. É só para testar as intuições de

vocês. Estudaremos algoritmos de

conversão entre Gramáticas e Autômatos no

próximo capítulo da matéria.

InformáticaPUC-Rio



ExercíciosSejam as gramáticas G1, G2, G3, G4 e G5, cujas regras de reescrita

são as seguintes:

1. Diga que tipo de gramática é cada uma delas, segundo a Hierarquia de Chomsky.

G1

S -> aS -> aS

G2

S -> ASbS ->SbA -> aA -> bA -> aA

G3

S -> ASS -> bA -> aA -> aA

G4

S -> ASBS -> cA -> aA -> aAB -> bB -> bB

G5

S -> XCX -> xX -> xXxxxX -> xxXxxxC -> xxC -> C

RegularTipo 3

Sensível aContextoTipo 1

Livre deContextoTipo 2 Livre de

ContextoTipo 2

IrrestritaTipo 0

InformáticaPUC-Rio



ExercíciosSejam as gramáticas G1, G2, G3, G4 e G5, cujas regras de reescrita são as

seguintes:

2. Mostre o caminho de derivação de pelos menos duas cadeias diferentes para cada uma delas, usando a notação do slide 5.

G1

S -> aS -> aS

G2


G3

S -> ASS -> bA -> aA -> aA

G4


G5


InformáticaPUC-Rio



Exemplos de DerivaçõesPara G1: • S -> a• S -> aS -> aaS -> aaa

Para G2:• S -> AS -> aS -> aAS -> abS -> aSb -> aASb -> aaSb -> …

Temos um problema com esta gramática; o processo de derivação não para. Podem tentar vários caminhos alternativos, todos levarão a pontos da derivação - …aS… ou …bS…-> …Sb… - que já foram visitados e de onde não se consegue sair. É um ciclo pernicioso que mostra que esta gramática está mal-formada.

Mais adiante na matéria procuraremos caracterizar ‘formalmente’ o sinal da má-formação desta gramática.

G1

S -> aS -> aS

G2


InformáticaPUC-Rio



Exemplos de DerivaçõesPara 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


InformáticaPUC-Rio



Algumas Derivações para G5

S -> XC -> xC -- parou a derivação aqui!S -> XC -> xXC -> xxC -> S -> XC -> xXC -> xxC -> C -- parou a derivação aqui!S -> XC -> xXC -> xxXC -> xxxC -> x S -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxxC -> xxS -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxXxC

-> xxXxxC -> xxX … (Ufa!) … -> xxxxxxxxxxxxxS -> XC -> xXC -> xxXC -> xxxXC -> xxXxC -> xxxXxC

-> xxXxxC -> xxXC…(Oh, não!)…<complete uma derivação você mesmo>

G5


InformáticaPUC-Rio



Explorando o JFLAP na derivação gramatical

Veja o vídeo de demonstração online.

Video S-aS.mp4

Video S-aS-derivacao.mp4

InformáticaPUC-Rio



Múltiplos caminhos de derivaçãoO importante é que a cada passo seja válida da “reescrita” realizada, isto é: que haja uma regra

autorizando a substituição. Diferentes caminhos têm, computacionalmente, diferentes vantagens e desvantagens, dependendo do propósito e do contexto da derivação.

Video S-aS-parsers.mp4

Vejam como a mesma cadeia é

aceita por 3 ‘parsers’

(analisadores sintáticos)

diferentes, que geram 3 árvores

diferentes!

Documents

Linguagens Formais e Autômatos (LFA)inf1626/docs/2013/extras/LFA-aula06-exercicios.pdf · qj = estado-alvo da transição defina formalmente o autômato A. Informática PUC-Rio ©Clarisse