FTC
Teoria da Computação
Gramáticas e Linguagens
Lucilia Figueiredo
Universidade Federal de Ouro Preto
DECOM-UFOP 2008
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramáticas
Exemplo de Gramática:
S → A
A → 0A1
A → Uma gramática consiste de uma coleção de regras que
especificam como derivar strings de uma linguagem.
As regras de produção envolvem símbolos da linguagem (ou
terminais) e variáveis (ou símbolos não-terminais), que
representam conjuntos de strings.
Uma das variáveis é distinguida como símbolo inicial.
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Derivação de String
Seja G1 a seguinte gramática:
S → A
A → 0A1
A → Exemplo de derivação de string usando G1 :
S ⇒ A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000111
A seqüência de substituições é chamada de derivação.
O conjunto de todos os strings de terminais gerados desta
forma constitui a linguagem especificada pela gramática.
Escrevemos L(G) para denotar a linguagem gerada pela
gramática G. Portanto, L(G1 ) = {0n 1n | n ≥ 0 }.
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramática - Definição Formal
Uma gramática G é uma tupla G = (V , Σ, R, S) onde:
V é um conjunto finito de símbolos, chamados de variáveis ou
não-terminais
Σ é um alfabeto, disjunto de V , cujos símbolos são chamados
de constantes ou terminais.
R é um conjunto finito de regras (ou produções) da forma
α → β, onde α ∈ (V ∪ Σ)+ , α contém pelo menos um símbolo
de V , e β ∈ (V ∪ Σ)∗
S ∈ V é o símbolo inicial.
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Gramática
G = ({S, A}, {0, 1}, R, S) onde R:
S → A
A → 0A1
A → Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Derivação
Se u, v , w ∈ (V ∪ Σ)∗ (i.e., são strings de variáveis e
terminais) e α → β ∈ R (i.e., é uma regra da gramática) então
dizemos que uαv deriva uβv , escrito como uαv ⇒ uβv .
Podemos também dizer que uβv é derivado diretamente de
uαv usando a regra α → β
u ⇒k v se existe uma seqüência finita
u0 , u1 , . . . , uk ∈ (V ∪ Σ)∗ , para k > 0, tal que
u = u0 ⇒ u1 ⇒ . . . ⇒ uk = v
Também dizemos que u0 , u1 , . . . , uk é uma derivação de v a
partir de u
Escrevemos u ⇒∗ v se u = v ou u ⇒k v para algum k > 0
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Linguagem Especificada por uma Gramática
Seja G = (V , Σ, R, S) uma gramática.
A linguagem especificada por G é
L(G) = {w ∈ Σ∗ | S ⇒∗ w }
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Tipos de Regras α → β
α
α∈V
α∈V
α∈V
α∈V
α∈V
α∈V
β
β=
β∈V
β ∈ Σ∗
β ∈ (V + )Σ∗
β ∈ Σ∗ (V + )
β ∈ Σ∗ (V + )Σ∗
α = uAv , β = uwv ,
u, v ∈ (V + Σ)∗ , A ∈ V , w ∈ (V + Σ)+
α≤β
Universidade Federal de Ouro Preto
Nome
-regra
unidade
terminal
linear a direita
linear a esquerda
linear
livre de contexto
sensível ao contexto
não-decrescente
irrestrita
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Tipos de Gramáticas - Hierarquia de Chomsky
Seja G = (V , Σ, R, S)
∀r ∈ R
r é linear à esquerda
r é linear à direita
r é linear
r é livre de contexto
r é sensível ao contexto
r é não-decrescente
r é irrestrita
Universidade Federal de Ouro Preto
L(G)
linear à esquerda
linear à direita
linear
livre de contexto
sensível ao contexto
não-decrescente
irrestrita
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Mais Notação
Para distinguir não-terminais de terminais, freqüentemente
usamos não-terminais entre < > e terminais entre aspas ” ”.
Se duas ou mais regras têm o mesmo lado esquerdo, por
exemplo, A → 0A1 e A → , podemos escrever, de forma mais
compacta A → 0A1 | .
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramática Livre de Contexto G2
A gramática G2 a seguir especifica um fragmento da língua inglesa:
<SENTENCE>
<NOUN_PHRASE>
<VERB_PHRASE>
<PREP_PHRASE>
<CP_NOUN>
<CP_VERB>
<ARTICLE>
<NOUN>
<VERB>
<PREP>
→
→
→
→
→
→
→
→
→
→
Universidade Federal de Ouro Preto
<NOUN_PHRASE><VERB_PHRASE>
<CP_NOUN> | <CP_NOUN><PREP_PHRASE>
<CP_VERB> | <CP_VERB><PREP_PHRASE>
<PREP><CP_NOUN>
<ARTICLE><NOUN>
<VERB> | <VERB><NOUN_PHRASE>
a | the
boy | girl | flower
touches | likes | sees
with
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramática Livre de Contexto G2
Note que:
A CFG G2 tem 10 variáveis (escritas em letras maiúsculas e
entra < >) e 9 não-terminais (escritos no alfabeto padrão),
mais um caractere de espaço.
A CFG G2 tem 18 regras.
Exemplos de strings que pertencem a L(G2):
a boy sees
the boy sees a flower
a girl with a flower likes the boy
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Derivação em G2
<SENTENCE>
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
<NOUN_PHRASE><VERB_PHRASE>
<CP_NOUN><VERB_PHRASE>
<ARTICLE><NOUN><VERB_PHRASE>
a <NOUN><VERB_PHRASE>
a boy <VERB_PHRASE>
a boy <CP_VERB>
a boy <VERB>
a boy sees
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Regras Lineares
Seja G = (V , Σ, R, S) uma CFG e A → w ∈ R, onde A ∈ V .
r é linear se w ∈ Σ∗ ◦ V ◦ Σ∗
r é linear à direita se w ∈ Σ∗ ◦ V
r é linear à esquerda se w ∈ V ◦ Σ∗
r é terminal se w ∈ Σ∗
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Gramática Linear à Direita
G = ({A, B}, {0, 1}, {A → 0A | B, B → 1B | }, A)
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Gramática Linear à Direita
G = ({A, B}, {0, 1}, {A → 0A | B, B → 1B | }, A)
Exemplo de derivação em G:
A ⇒ 0A ⇒ 00A ⇒ 00B ⇒ 001B ⇒ 0011B ⇒ 00111B ⇒ 00111
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Gramática Linear à Direita
G = ({A, B}, {0, 1}, {A → 0A | B, B → 1B | }, A)
Exemplo de derivação em G:
A ⇒ 0A ⇒ 00A ⇒ 00B ⇒ 001B ⇒ 0011B ⇒ 00111B ⇒ 00111
Qual é a linguagem especificada por G?
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo de Gramática Linear à Direita
G = ({A, B}, {0, 1}, {A → 0A | B, B → 1B | }, A)
Exemplo de derivação em G:
A ⇒ 0A ⇒ 00A ⇒ 00B ⇒ 001B ⇒ 0011B ⇒ 00111B ⇒ 00111
Qual é a linguagem especificada por G?
L(G) = 0∗ 1∗
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
DFA ⇒ Gramática Linear à Direita
Teorema
Seja L ⊆ Σ∗ uma linguagem regular. Então existe uma Gramática
Linear à Direita G tal que L(G) = L.
Prova: Por construção. Como L é regular, existe um DFA
M = (Q, Σ, δ, q0 , F ) tal que L(M) = L e Σ ∩ Q = ∅. Construa
G = (Q, Σ, R, q0 ) tal que
R = {q → aq 0 | a ∈ Σ ∧ δ(q, a) = q 0 } ∪ {q → | q ∈ F }
1
G é linear à direita e simula M diretamente
2
Se x = x1 x2 · · · xn ∈ L(M) com δ(q0 , x1) = q1, δ(q1 , x2) = q2, . . .,
δ(qn−1 , xn ) = qn , então q0 ⇒ x1 q1 ⇒ x1 x2 q2 ⇒ · · · x1 x2 · · · xn qn
3
Como qn ∈ F então qn → ∈ R e x1 x2 · · · xn ∈ L(G)
4
Portanto L(G) = L(M)
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramática Linear à Direita - Lema
Lema
Para cada gramática linear à direita G = (V , Σ, R, S), existe uma
gramática linear à direita G0 = (V 0 , Σ, R 0 , S) onde toda regra não
terminal A → w ∈ R é tal que |w| ≤ 2 e toda regra terminal
A → u ∈ R é tal que |u| ≤ 1.
Idéia da prova Note que G0 pode incluir regras da forma A → A ou A → ( pode pertencer a uma linguagem regular). Transforme cada regra
A → x1 , x2 , · · · xn B ∈ R com n > 1 no seguinte conjunto de regras, onde
A1 , A2 , . . . An−1 são variáveis novas:
A
A1
..
.
→
→
x1 A1
x2 A2
An−1
→
xn B
A mesma idéia é usada para regras terminais A → u com |u| > 1.
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo
Seja G = ({A, B}, {a, b}, {A → abA | abB, B → aaaB|b}, A).
A gramática equivalente G0 tal como no lema anterior é
G0 = ({A, X 1, Y 1, B, Z 1, Z 2}, {a, b}, R 0 , A) onde R 0 é:
A
X1
Y1
B
Z1
Z2
Universidade Federal de Ouro Preto
→
→
→
→
→
→
aX1 | aY 1
bA
bB
aZ1 | b
aZ2
aB
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Gramática Linear à Direita ⇒ DFA
Teorema
Se G é uma gramática linear à direita, então L(G) é regular
Prova: por construção.
1
Seja G = (V , Σ, R, S). Usando o Lema anterior podemos supor que
R tem apenas produçãoes da forma A → aB ou A → a, onde
A, B ∈ V e a ∈ Σ ∪ {}.
2
Um NFA M que reconhece L(G) é M = (V ∪ {Θ}, Σ, δ, S, {Θ}) onde,
para cada A ∈ V e cada a ∈ Σ ∪ {}:
se A → a ∈ R então δ(A, a) = {Θ} ∪ {B | A → aB ∈ R}
se A → a 6∈ R então δ(A, a) = {B | A → aB ∈ R}
3
Pode-se verificar diretamente que L(M) = L(G)
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Exemplo
O NFA M que aceita a linguagem especificada pela gramática
linear à direita G0 construída anteriormente é:
b
A
a
a
b
X1
Universidade Federal de Ouro Preto
b
Y1
Z1
B
b
Θ
a
a
Z2
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Observações - 1
Existe uma dualidade perfeita entre reconhecimento e
geração de linguagens regulares: um reconhecedor realiza
uma transição atômica, e consome um único símbolo, quando
a regra da gramática é usada em um passo atômico,
produzindo um símbolo.
Os resultados estabelecidos para gramáticas lineares à direita
valem também para gramáticas lineares à esquerda:
Teorema: Uma linguagem é linear à direita se, e somente se,
ela é linear à esquerda.
O termo Gramática Regular é usado para designar uma
gramática que é linear à direita ou linear à esquerda.
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc
FTC
Observações - 2
Os resultados estabelecidos para Gramáticas Regulares
mostram que toda linguagem Regular é Livre de Contexto.
Entretanto, como já sabemos a linguagem L = {0n 1n | n ≥ 0}
é livre de contexto mas não é regular. Uma CFG que gera
L = {0n 1n | n ≥ 0} é:
G = ({S}, {0, 1}, {S → 0S1 | }, S)
Ou seja, nem toda linguagem livre de contexto é regular.
Portanto RL ⊂ CFL
Universidade Federal de Ouro Preto
www.dcc.ufmg.br/~lucilia/cursos/ftc