Gramatyki bezkontekstowe
Definicja: Gramatyka bezkontekstowa G to czwórka
G = (N, T , P, S) gdzie
N - skończony zbiór zmiennych (nieterminale),
Gramatyki bezkontekstowe
T - skończony zbiór symboli końcowych (terminale,
Języki formalne i techniki translacji - Wykład 4
alfabet),
P - skończony zbiór produkcji postaci A ą, gdzie A " N
i ą " (N *" T )",
Maciek Gębala
S " N - symbol początkowy.
Relacja wyprowadzenia �!
13 marca 2013 G
Jeśli A � jest produkcją w G i ą, ł " (N *" T )" to ąAł �! ą�ł
G
(ą�ł jest bezpośrednio wyprowadzany z ąAł w gramatyce G).
Będziemy pisać tylko �! gdy gramatyka jest oczywista.
�!"  zwrotne i przechodnie domknięcie �!.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Gramatyki bezkontekstowe Drzewo wyprowadzenia
Definicja: Język generowany przez G to
Drzewo o następujących własnościach
"
L(G) = { w : w " T '" S �!" w }.
G 1
każdy wierzchołek ma etykietę z N *" T *" {�},
2
korzeń ma etykietę S (symbol początkowy),
Język L nazywamy bezkontekstowym jeśli jest identyczny z L(G) dla
3
pewnej gramatyki bezkontekstowej G. wierzchołki wewnętrzne mają etykiety z N,
G1 i G2 są równoważne jeżeli L(G1) = L(G2).
4
jeżeli wierzchołek wewnętrzny ma etykietę A a jego synowie od
lewej mają kolejno etykiety X1, . . . , Xn to A X1 . . . Xn jest
Przykład
produkcją w P.
G = ({S}, {0, 1}, {S �, S 0, S 1, S 0S0, S 1S1}, S)
Jeśli konkatenacja wszystkich liści czytanych od lewej do prawej daje
ą to drzewo nazywamy drzewem wyprowadzenia ą.
lub inaczej (krócej) zapisując
Przykład drzewa wyprowadzenia (na tablicy)
S �|0|1|0S0|1S1
Słowo id + id " id dla gramatyki E E + E|E " E|id.
Wyprowadzenie słowa 0110:
S �! 0S0 �! 01S10 �! 0110
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Drzewo wyprowadzenia Usuwanie symboli bezużytecznych
Twierdzenie. Niech G = (N, T , P, S) będzie gramatyką
bezkontekstową. Wtedy S �!" ą �!�! istnieje drzewo
wyprowadzenia ą w gramatyce G.
Niech L  niepusty język bezkontekstowy. Wtedy L można
wygenerować za pomocą gramatyki G o następujących własnościach
Dowód
Indukcja względem ilości wierzchołków wewnętrznych w drzewie. 1
każdy symbol pojawia się w wyprowadzeniu jakiegoś słowa z L,
2
nie ma produkcji postaci A B (produkcje jednostkowe), gdzie
A, B " N.
Definicja. Jeżeli w każdym kroku wyprowadzenia stosujemy
produkcję do nieterminala leżącego najbardziej na lewo (prawo), to
Co więcej, jeśli � " L to w G nie ma produkcji postaci A �.
/
wyprowadzenie nazywamy lewostronnym (prawostronnym).
Jeżeli w " L(G) to w ma co najmniej jedno drzewo wyprowadzenia.
Symbol X jest użyteczny jeśli istnieje wyprowadzenie postaci
Każdemu drzewu wyprowadzenia odpowiada dokładnie jedno
"
S �!" ąXł �!" w (w " T ), w p.p. X jest bezużyteczny.
wyprowadzenie lewostronne (prawostronne).
Definicja. Jeśli w L(G) istnieje słowo mające dwa różne drzewa
wyprowadzenia to G nazywamy wieloznaczną.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Usuwanie symboli bezużytecznych Usuwanie symboli bezużytecznych
Lemat. Dla dowolnej gramatyki bezkontekstowej G = (N, T , P, S)
można efektywnie znalez
ć równoważną gramatykę bezkontekstową
Lemat. Dla dowolnej gramatyki bezkontekstowej G = (N, T , P, S)

G = (N , T , P , S) t.że dla każdego X " (N *" T ) istnieją
z L(G) = " można efektywnie znalez
ć równoważną gramatykę


ą, � " (N *" T )" t.że S �!" ąX �.
bezkontekstową G = (N , T , P , S) t.że dla dowolnego A " N istnieje
"
w " T t.że A �!" w.
Dowód (szkic)
1
Dowód (szkic)
N �! {S}
2
1
można zmienić N
Ns �! "
"
Jeśli A " N i A ą1| . . . |ąn to dodaj wszystkie nieterminale
Nn �! {A : (A w) " P '" w " T }

z ą1, . . . , ąn do N a terminale do T .
2
Ns = Nn

3
Do P przenieś tylko te produkcje z P które zawierają symbole
Ns �! Nn

z N *" T *" {�}.
Nn �! Ns *" {A : (A ą) " P '" ą " (T *" Ns)"}
3
N �! Nn
P �! {(A ą) " P : A " Nn '" ą " (T *" Ns)"}
Twierdzenie. Każdy niepusty język bezkontekstowy jest generowany
przez gramatykę bezkontekstową nie zawierającą symboli
bezużytecznych.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Usuwanie �-produkcji Usuwanie produkcji jednostkowych
Twierdzenie. Jeżeli L = L(G) dla gramatyki bezkontekstowej
Twierdzenie. Każdy język bezkontekstowy nie zawierający � jest
G = (N, T , P, S) to dla L \ {�} istnieje gramatyka bezkontekstowa G
definiowany za pomocą gramatyki nie zawierającej symboli
nie zawierająca �-produkcji i symboli bezużytecznych.
bezużytecznych, �-produkcji i produkcji jednostkowych.
Dowód
Dowód
Symbole bezużyteczne usunęliśmy dzięki poprzedniemu twierdzeniu.
Jeżeli dla nieterminala A mamy A �!" B i A = B to dla każdej

Dla każdego nieterminala A sprawdzamy czy A �!" �. Jeśli tak to
niejednostkowej produkcji B ą dodajemy produkcję A ą.
każdą produkcję B ąA� zastępujemy produkcjami B ąA�
Następnie usuwamy produkcje jednostkowe.
i B ą� (ale nie dołączamy B �). Następnie usuwamy wszystkie
�-produkcje.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Postać normalna Chomsky ego Przykład
S bA|aB
Twierdzenie. Dowolny język bezkontekstowy nie zawierający � jest
generowany przez gramatykę której wszystkie produkcje są postaci
A bAA|aS|a
A BC lub A a, gdzie A, B, C " N i a " T .
B aBB|bS|b
Dowód (konstrukcja)
Niech G będzie gramatyką bez symboli bezużytecznych, �-produkcji
Przykład na tablicy.
i produkcji jednostkowych. Wtedy jeśli prawa strona produkcji jest
długości 1 to jest postaci A a. Dla pozostałych produkcji
Postać normalna Chomsky ego
wykonujemy następujące operacje:
1
S CbA|CaB
Jeśli po prawej stronie występuje terminal a to dodajemy do N
nowy nieterminal Ca a do produkcji Ca a i zastępujemy a
A CbDA|CaS|a
przez Ca.
B CaDB|CbS|b
2
Teraz jeśli prawa strona produkcji jest dłuższa niż 1 to zawiera
Ca a
tylko nieterminale. Jeśli jest postaci A B1 . . . Bn dla n > 2, to
Cb b
tworzymy nowe nieterminale D1, . . . , Dn-2 i zastępujemy tą
DA AA
produkcję przez
A B1D1, D1 B2D2, . . . , Dn-3 Bn-2Dn-2, Dn-2 Bn-1Bn.
DB BB
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Postać normalna Greibach Postać normalna Greibach
Produkcje są postaci A aą, gdzie A " N, a " T i ą " N".
Lemat 2. Niech G = (N, T , P, S) będzie gramatyką bezkontekstową.
Niech A Aą1| . . . |Aąr będzie zbiorem tych A-produkcji których
Określmy jako A-produkcje wszystkie produkcje z nieterminalem A po
prawe strony zaczynają się od A. Niech A �1| . . . |�s będzie
lewej stronie.
zbiorem pozostałych A-produkcji. Niech G = (N *" {B}, T , P , S)
będzie gramatyką utworzoną poprzez dodanie nowego nieterminala
Lemat 1. Niech G = (N, T , P, S) będzie gramatyką bezkontekstową.
B i zastąpienie wszystkich A-produkcji przez następujące produkcje
Niech A ą1Bą2 będzie produkcją w P i niech B �1| . . . |�r będzie
zbiorem wszystkich B-produkcji. Niech G = (N, T , P , S) będzie
A �i|�iB, 1 i s
gramatyką otrzymaną z G przez usunięcie produkcji A ą1Bą2
i dodanie produkcji A ą1�1ą2| . . . |ą1�r ą2. Wówczas L(G) = L(G ). B ąj|ąjB, 1 j r
Wtedy L(G) = L(G ).
Dowód
Dowód po strukturze drzewa wyprowadzenia.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Postać normalna Greibach Postać normalna Greibach
Twierdzenie. Każdy język bezkontekstowy L nie zawierający � jest
generowany przez pewną gramatykę w której każda produkcja jest
postaci A aą, gdzie a " T , A " N i ą " N".
Dowód
W wyprowadzeniu lewostronnym ciąg produkcji postaci A Aąi musi
Dowód
kiedyś skończyć się produkcją A �j
Niech G = (N, T , P, S) będzie gramatyką w postaci normalnej
A �! Aąi �! Aąi ąi �! . . . �! Aąi . . . ąi �! �jąi . . . ąi
1 2 1 n 1 n 1 Chomsky ego. Załóżmy, że N = {A1, . . . , An}.
Modyfikujemy produkcje tak aby jeśli produkcja jest postaci Ai Ają
Można to zastąpić przez
to i < j.
A �! �jB �! �jąi B �! . . . �! �jąi . . . ąi B �! �jąi . . . ąi k 1 n
n n 2 n 1
j 1 k - 1
Ponieważ transformacja ta jest obustronna to L(G) = L(G )
1
Za każdą produkcję postaci Ak Ają wstaw produkcje Ak �ą
dla wszystkich produkcji Aj � (Lemat 1).
2
Dla produkcji postaci Ak Aką wykonaj Lemat 2 używając
nieterminal Bk.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Postać normalna Greibach Przykład
Dowód cd.
A1 A2A3
Po wykonaniu tego algorytmu mamy gramatykę równoważną
A2 A3A1|b
o produkcjach w postaci:
1
A3 A1A2|a
Ai Ajł, gdzie zawsze i < j,
2
Ai ał, gdzie a " T ,
3
Bi ł, gdzie ł " (N *" {B1, . . . , Bi-1})". Nie pasuje A3 A1A2 więc z Lematu 1 dostajemy A3 A2A3A2.
Zauważmy, że An-produkcje muszą zaczynać się terminalem. Teraz
rozważmy Am-1-produkcje: ich lewe strony muszą zaczynać się
Dalej nie pasuje więc ponownie z Lematu 1 otrzymujemy
terminalem lub nieterminalem Am więc możemy je z Lematu 1
A3 A3A1A3A2|bA3A2.
zastąpić prawymi stronami Am-produkcji (wszystkie zaczynają się
terminalem). I tak do A1.
Teraz mamy A3 A3A1A3A2|bA3A2|a, korzystamy z Lematu 2
A
atwo zauważyć że B-produkcje nigdy nie zaczynają się
i otrzymujemy A3 a|aB3|bA3A2|bA3A2B3 i B3 A1A3A2|A1A3A2B3.
nieterminalem B więc też z Lematu 1 możemy je zastąpić prawymi
stronami A-produkcji.
Maciek Gębala Gramatyki bezkontekstowe Maciek Gębala Gramatyki bezkontekstowe
Przykład
Teraz odpowiednio podstawiając zgodnie z Lematem 1 otrzymujemy
A3 a|aB3|bA3A2|bA3A2B3
A2 aA1|aB3A1|bA3A2A1|bA3A2B3A1|b
A1 aA1A3|aB3A1A3|bA3A2A1A3|bA3A2B3A1A3|bA3
B3 aA1A3A3A2|aB3A1A3A3A2|bA3A2A1A3A3A2|
bA3A2B3A1A3A3A2|bA3A3A2|aA1A3A3A2B3|
aB3A1A3A3A2B3|bA3A2A1A3A3A2B3|
bA3A2B3A1A3A3A2B3|bA3A3A2B3
Maciek Gębala Gramatyki bezkontekstowe