Lemat o pompowaniu dla języków bezkontekstowych
Lemat. Niech L będzie dowolnym językiem bezkontekstowym. Wtedy
istnieje stała n, zależna tylko od L, taka że jeśli z należy do L i |z| n
to z = uvwxy, i
Własności języków bezkontekstowych
1
|vx| 1,
Języki formalne i techniki translacji - Wykład 6
2
|vwx| n,
3
dla każdego i 0 uviwxiy " L.
Maciek Gębala
Dowód
27 marca 2013
Na tablicy.
Lemat wykorzystywany do udowadniania że język nie jest
bezkontekstowy.
Maciek Gębala Własności języków bezkontekstowych Maciek Gębala Własności języków bezkontekstowych
Przykład Lemat Ogdena - silniejsza wersja lematu o
pompowaniu
L = { aibici : i 1 }
Lemat. Niech L będzie językiem bezkontekstowym. Wtedy istnieje
Dowód że L nie jest bezkontekstowy
stała n taka że jeśli w z " L oznaczymy co najmniej n liter to możemy
Wez
my n z lematu i słowo z = anbncn.
z zapisać jako uvwxy i
1) Zgodnie z lematem możemy pompować w obrębie jednego bloku
1
v i x majÄ… Å‚Ä…cznie co najmniej jednÄ… oznaczonÄ… literÄ™,
znaków (a lub b lub c) ale wtedy zmienia się ilość tych znaków a nie
2
zmienia się pozostałych, czyli wychodzimy z języka. vwx ma co najwyżej n oznaczonych liter,
2) Możemy pompować też znaki z dwóch sąsiednich bloków (a i b lub
3
dla każdego i 0 uviwxiy " L.
b i c) utrzymując ich równoliczność, ale wtedy zostaje problem
z trzecim blokiem i także wypadamy z języka.
Dowód
3) Innych możliwości nie ma więc L nie jest bezkontekstowy.
A co z następującym językiem
Na tablicy.
L = { aibjck : i = j '" j = k }

Maciek Gębala Własności języków bezkontekstowych Maciek Gębala Własności języków bezkontekstowych
Przykład Własności języków bezkontekstowych
Twierdzenie. Języki bezkontekstowe są zamknięte na sumę,
L = { aibjck : i = j '" j = k }

złożenie i domknięcie Kleene ego.
Dowód że L nie jest bezkontekstowy
Dowód
Wez
my n z lematu i m > n. Wez
my z = am+m!bmcm+m! i oznaczmy
G1 = (N1, T1, S1, P1) i G2 = (N2, T2, S2, P2), N1 )" N2 = " i
wszystkie litery b.
S " N1 *" N2.
A
atwo zauważyć, że zgodnie z lematem musimy pompować co
G3 = ({S} *" N1 *" N2, T1 *" T2, S, P1 *" P2 *" {S S1|S2})
najmniej jedno b i nie możemy pompować jednocześnie a i c.
i L(G3) = L(G1) *" L(G2)
Załóżmy, że pompujemy 1 k n symboli b i nie pompujemy
G4 = ({S} *" N1 *" N2, T1 *" T2, S, P1 *" P2 *" {S S1S2})
symboli c. Wtedy dla i = 1 + m!/k mamy m + m! symboli b i słowo
i L(G4) = L(G1)L(G2)
wypada z języka. Analogicznie jeśli nie pompujemy a.
G5 = ({S} *" N1, T1, S, P1 *" {S S1S|µ}) i L(G5) = L(G1)"
Maciek Gębala Własności języków bezkontekstowych Maciek Gębala Własności języków bezkontekstowych
Własności języków bezkontekstowych
Twierdzenie. Języki bezkontekstowe nie są zamknięte na przecięcie.
Dowód
{aibici} = {aibicj} )" {ajbici}
Wniosek. Języki bezkontekstowe nie są zamknięte na dopełnienie.
Twierdzenie. Jeśli L - język bezkontekstowy i R - język regularny to
L )" R - język bezkontekstowy.
Maciek Gębala Własności języków bezkontekstowych