Embed Size (px)
Citation preview
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 1
Linguagens Formais e Autômatos (LFA)Linguagens Formais e Autômatos (LFA)
Aula de 16/10/2013Aula de 16/10/2013
Linguagens Livres de ContextoLinguagens Livres de Contexto
©Clarisse S. de Souza, 2013 1
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 2
Características Formais da LLC’sLinguagens Livres de Contexto (LLC’s) são classificadas como linguagens de
tipo 2, na Hierarquia de Chomsky
Suas produções têm por característica padrões do tipo
onde:1.
|| = 1 e
é
um símbolo não-terminal da linguagem2.
é
uma cadeia qualquer de terminais e não-terminais
Ramos e co-autores (2009) p. 299
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 3
Aninhamento: Marca Registrada das LLC’s
Ramos e co-autores (2009) p. 300
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 4
Linguagens ESTRITAMENTE Livres de Contexto
Ramos e co-autores (2009) p. 300
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 5
Linguagens ESTRITAMENTE Livres de Contexto
Ramos e co-autores (2009) p. 301
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 6
Expressão de Padrões Sonoros (Linguagem RExpressão de Padrões Sonoros (Linguagem Ríítmica)tmica)
©Clarisse S. de Souza, 2013 6
S
tempo, tempo |S
tempo, tempo, Stempo
| ||
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 7
Expressão de Padrões Visuais (Imagem Fractal)Expressão de Padrões Visuais (Imagem Fractal)
©Clarisse S. de Souza, 2013 7
S S1
S2 S3
S4
Curva de Koch
(L System)
S1
SS2
SS3
SS4
S A imagem fractal exata tem uma particularidade em relação à
gramáticaao lado: seus nós-filhos de mesmo nível
têm de ser raiz de sub-árvores de
igual profundidade (altura).
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 8
Expressão de Padrões Linguísticos
S Frase Nominal, Verbo, Preposição, Frase Nominal
Frase Nominal
‘Pedro’
| ‘Joana’
| Artigo, NomeVerbo
‘trabalha’
| ‘joga’
| ‘mora’
Preposição
‘com’Artigo
a
Nome
menina
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 9
Expressão de Padrões Linguísticos
S Frase Nominal, Verbo, Preposição, Frase Nominal
Frase Nominal
‘Pedro’
| ‘Joana’
| Artigo, NomeVerbo
‘trabalha’
| ‘joga’
| ‘mora’
Preposição
‘com’Artigo
a | o
Nome
menina | menino
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 10
Expressão de Padrões Linguísticos
S Frase Nominal, Verbo, Preposição, Frase Nominal
S
‘que’, Verbo, Preposição, Frase, Nominal
Frase Nominal
‘Pedro’
| ‘Joana’
| Artigo, Nome | SVerbo
‘trabalha’
| ‘joga’
| ‘mora’
Preposição
‘com’Artigo
a
Nome
menina
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 11
Quais das linguagens ilustradas são estritamente LLC’s?
A Linguagem Rítmica?A Linguagem Visual?A Linguagem (pseudo)Natural?
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013INF1626 Linguagens Formais e Autômatos (2013--2)2)
©Clarisse S. de Souza, 2013 12
Exercício
Considere que os termos “a”, “b”, “c”, “d”, “e”
são variáveis booleanas de uma linguagem de programação.
Considere também que, com os conectivos “AND”, “OR”
e “NOT”
podem-se montar expressões booleanas, as
quais podem conter sub-expressões delimitadas por parênteses balanceados. Exemplo: “(a AND ((b OR c OR d) OR (d AND e)))”
Escreva uma Gramática Livre de Contexto (GLC) para caracterizar tais expressões booleanas.
