Det finns flera sätt att visa att ett språk inte är kontextfritt. De vanligaste metoderna förlitar sig på att bevisa att språket bryter mot egenskaper som är inneboende till kontextfria språk (CFL):
1. Pumpande lemma för kontextfria språk: Detta är den mest använda tekniken. Pumpens lemma säger att för alla Cfl l finns det en konstant * p * (pumplängden) så att alla strängar * w * i l med längd | w | ≥ *p *kan skrivas som *uvxyz *, där:
* | Vxy | ≤ *p *
* | Vy | ≥ 1
* * uv
i
xy
i
z* ∈ L för alla* i* ≥ 0
För att bevisa att ett språk är * inte * kontextfritt med hjälp av pumpens lemma:
1. Antag: Antag, för motsägelse, att språket * l * är kontextfritt.
2. Välj en sträng: Välj en sträng *w *i *l *med längd åtminstone pumplängden *p *(du måste ofta strategiskt välja *w *).
3. pumpa strängen: Försök att sönderdelas * w * i * uvxyz * tillfredsställa lemmas förhållanden.
4. Hitta en motsägelse: Visa att för vissa *i *, *uv
i
xy
i
z*är*inte*i*l*. Detta strider mot pumpens lemma, vilket bevisar att det ursprungliga antagandet (att * l * är kontextfritt) måste vara falskt.
Exempel: Låt oss överväga språket l ={a
n
b
n
c
n
| n ≥ 0}. Använda pumpens lemma:
1. Antag: L är kontextfri.
2. Välj en sträng: Låt * w * =a
p
B
p
c
p
(där * p * är pumplängden).
3. pumpa strängen: Oavsett hur du sönderdelas *w *till *uvxyz *, kommer pumpen oundvikligen att kränka a
n
b
n
c
n
strukturera. Till exempel, om * vxy * bara innehåller 'A, kommer pumpen att öka antalet' A:er utan att öka antalet 'B:er och' c. Liknande problem uppstår om * vxy * bara innehåller 'B:er eller' c eller en blandning som inte upprätthåller lika förhållandet.
4. Motstånd: Därför finns det en *i *så att *uv
i
xy
i
z* ∉ l, motsäger pumpens lemma. Således är L inte kontextfri.
2. Stängningsegenskaper: Kontextfria språk stängs under vissa operationer (Union, Concatenation, Kleene Star, korsning med ett regelbundet språk). Om du kan visa att ett språk är * inte * stängt under en av dessa operationer kan det inte vara kontextfritt. Denna metod används mindre ofta för direkt bevis än pumpande lemma men kan vara till hjälp i kombination med andra tekniker.
3. Ogdens Lemma: Detta är en kraftfullare version av pumpande lemma, så att du kan välja markerade positioner i strängen *w *. Det är användbart för språk där det enkla pumpande lemmaet är svårt att applicera.
4. Parikhs sats: Detta teorem hänför sig till antalet förekomster för varje symbol i strängar på ett språk. Även om det inte direkt används för att bevisa ett språk * är inte * kontextfritt, kan det ibland hjälpa till att visa att ett språkstruktur är oförenligt med de begränsningar som CFL sätter. Det används ofta i samband med andra tekniker.
Sammanfattningsvis är det pumpande lemma den vanligaste och generellt effektiva metoden för att bevisa att ett språk inte är kontextfritt. Valet av metod beror emellertid på det specifika språkets struktur och den enkelhet som varje teknik kan tillämpas med. Ogdens Lemma erbjuder mer kraft vid behov, och stängningsegenskaper kan ge kompletterande bevis.
