Linguagens Formais e Aut matos Aula 2 Gram ticas Introdu o 23.08.2017

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Gramáticas – Introdução
• Também conhecidas como dispositivos
generativos, dispositivos de síntese.
• Portanto, Gramática é considerado um
formalismo de geração, pois permite derivar
(“gerar”) todas as palavras da linguagem que
representa.
• Ou ainda dispositivos de geração de cadeias.
• As gramáticas constituem sistemas formais
baseados em regras de substituição, através dos
quais é possível sintetizar, de forma exaustiva, o
conjunto das cadeias que compõem uma
determinada linguagem.
• Definir sentenças válidas para uma linguagem e
fornecer uma definição estrutural para tais
sentenças.
• A perspectiva generativa define um conjunto de
regras para que todas as cadeias admissíveis
possam ser geradas.
• A notação formal de gramática foi introduzida
pelo linguista Avram Noam Chomsky em 1950.
Definição: Uma gramática (ou sistema de
reescritura) é uma 4-upla G = (V,Σ, R, S), onde:
• V é um conjunto finito não vazio de símbolos
não terminais (variáveis).
• Σ é um conjunto finito não vazio de símbolos,
disjunto de V, cujos elementos são denominados
símbolos terminais (alfabeto).
Definição: Uma gramática (ou sistema de
reescritura) é uma 4-upla G = (V,Σ, R, S), onde:
• R é um conjunto de regras de substituição ou
reescritura ou produção (P), da gramática.
 na forma u ↦ v, onde u e v são palavras sobre
V ∪ Σ, com certas restrições conforme o tipo
da gramática.
• S ∈ V é o símbolo inicial (símbolo de partida ou
variável inicial).
Definição: Uma Linguagem Gerada pela Gramática
G = (V, Σ, R, S), denotada por L(G) ou GERA(G), é
composta por todas as palavras de símbolos
terminais deriváveis a partir do símbolo inicial S, ou
seja:
L(G) = {w  * | S ↦ +w}
Observação: Derivação é a substituição de uma
subpalavra de acordo com uma regra de produção.
Definição: Duas Gramáticas G1 e G2 são ditas
equivalentes se, e somente se, as linguagens
geradas forem equivalentes, ou seja, L(G1) = L(G1)
ou GERA(G1) = GERA(G2).
Exemplo 1: G = (V,Σ, R, S), onde:
• V = {S}
• Σ = {a, b}
• R = {S ↦(1) aSb, S ↦(2) }
• Quais palavras podemos derivar (geradas) dessa regra
de produção, dessa gramática?
• A partir do símbolo inicial podemos aplicar as regras de
produção.
Observação: Adotam-se também as representações:
• G = (V,Σ, P, S) ou G = (V, T, P, S)
Exemplo 1: G = (V,Σ, R, S), onde:
• V = {S}
• Σ = {a, b}
• R = {S ↦(1) aSb, S ↦(2) }
S  (1) aSb  (1) aaSbb  (1) aaaSbbb  (2) aaabbb
Forma Sentencial Sentença
L(G) = {anbn | n  0}
Exemplo 2: G = (V,Σ, R, S), onde:
• V = {A,B,S}
• Σ = {0, 1}
• R = {S ↦ AB (1), A ↦ 0A11 (2), A ↦  (3), B ↦ 0B (4), B ↦ 
(5)}
S  (1) AB (2) 0A11B  (3) 011B  (5) 011
S  (1) AB (2) 0A11B  (2) 00A1111B  (3) 001111B
 (4) 0011110B  (5) 0011110
L(G) = {0n12n0m | n  0, m  0}
Exemplo 3: Seja G = ({S, A, B}, {a, b}, R, S)
Onde:
• R = {S ↦(1) SAB, S ↦(2) SBA, S ↦(3) , A ↦(4) aAB, A
↦(5) aBA,A ↦(6) a, B ↦(7) bAB, B ↦(8) bBA, B ↦(9) b}.
• Um string gerado por G é w = bbaabaab, pois:
• S ⇒(1)SAB ⇒(2)SBAAB ⇒(3)BAAB ⇒(8)bBAAAB
⇒(9)bbAAAB ⇒(4)bbaABAAB ⇒(6)bbaaBAAB
⇒(9)bbaabAAB ⇒(6)bbaabaAB ⇒(6)bbaabaaB
⇒(9)bbaabaab = w.
• Esta gramática gera palavras com o mesmo número de
a’s e b’s.
Exemplo 4: Seja G = ({S, X,Y, A, B, F}, {a, b}, P, S)
Onde:
• P = {S ↦ XY,
X ↦ XaA | XbB | F,
Aa ↦ aA, Ab ↦ bA,AY ↦Ya,
Ba ↦ aB, Bb ↦ bB, BY ↦Yb,
Fa ↦ aF, Fb ↦ bF, FY ↦ }.
A Gramática gera a linguagem cujas palavras são tais que a
primeira metade é igual a segunda metade.
L(G) = {ww | w é palavra de {a, b}*}
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Gramáticas – Introdução