Hur kan pumpens lemma användas för att bevisa att ett språk inte är kontextfritt?

Pumping Lemma för kontextfria språk (CFLS) är ett kraftfullt verktyg för att bevisa att ett givet språk är * inte * kontextfritt. Det är ett bevis med motsägelse -teknik. Här är den allmänna processen och de viktigaste idéerna:

1. Ange det pumpande lemmaet (noggrant!)

Innan du börjar är det viktigt att förstå Pumping Lemmas uttalande *exakt *. Här är en vanlig formulering:

Pumpande lemma för CFL:

Om L är ett kontextfritt språk, finns det ett heltal *P *("Pumplängden") så att för alla strängar *i L med längd större än eller lika med *P *(| S | ≥ *P *) kan *S *delas upp i fem substrängar:*S =Uvxyz *, tillfredsställer följande villkor:

* | Vxy | ≤ * p * (den mellersta delen som pumpas är inte för lång)

* | Vy | ≥ 1 (det pumpade avsnittet är inte tomt)

* För alla * i * ≥ 0, * uv ⁱ xy ⁱ z* är också i L (pumpning 'v' och 'y'. Några gånger som håller strängen på språket)

2. Anta att språket * är * kontextfritt

Börja med att anta, för motsägelse, att språket *l *du vill bevisa är *inte *kontextfritt *är *, i själva verket, kontextfri. Detta är det första antagandet som du så småningom kommer att motbevisa.

3. Låt * p * vara pumplängden

Eftersom du har antagit att * l * är kontextfri, måste pumpens lemma * * applicera. Detta innebär att det finns en pumplängd * P * (som du inte vet det exakta värdet på). Det är avgörande att komma ihåg att motståndaren (som vet att språket är *inte *kontextfritt och försöker lura dig) får välja *p *. Ditt mål är att hitta en sträng som * Oavsett vilket värde på p * väljs leder villkoren för pumpens lemma till en motsägelse.

4. Välj en sträng*s*∈*l*så att |*s*| ≥ *p *

Detta är ett kritiskt steg. Du måste noggrant välja en sträng *S *som tillhör språket *l *och har en längd som är större än eller lika med *p *. Valet av * s * är avgörande för att få beviset att fungera. Tänk på strukturen på strängarna på ditt språk och hur pumpning kan påverka den strukturen. Målet är att välja en sträng vars egenskaper kommer att kränkas när 'V' och 'Y' pumpas på ett sätt som dikteras av den pumpande lemma. Detta val *involverar ofta *att ställa in vissa delar av strängen baserat på värdet *p *.

*Tänk på de egenskaper som gör strängar på språket tillhör det. Välj sedan en sträng på ett sådant sätt att när någon understräng pumpas, kränks åtminstone en av begränsningarna för språkmedlemskapet.*

5. Tänk på alla möjliga nedbrytningar * s =uvxyz * tillfredsställande | vxy | ≤ * p * och | vy | ≥ 1

Pumpande lemma säger att*alla*strängar*S*med |*S*| ≥ * p * kan delas på detta sätt. Så, * din motståndare * får välja hur * s * är uppdelat i * uvxyz * (med förbehåll för begränsningarna | vxy | ≤ * p * och | vy | ≥ 1). Men du får överväga alla möjliga sådana uppdelningar. Du måste visa att *Oavsett hur *motståndaren väljer *u *, *v *, *x *, *y *och *z *, kan du pumpa strängen för att få en motsägelse.

Ofta innebär detta att överväga olika *fall *baserat på var *v *och *y *kan potentiellt falla inom strängen *s *. För varje fall analyserar du vad som händer när du pumpar *V *och *y *.

6. Visa att för vissa *i *≥ 0, strängen *uv ⁱ xy ⁱ z * är * inte * i * l *

Detta är kärnan i motsägelsen. För varje fall som beaktas i steg 5 måste du visa att det finns några *i *(vanligtvis *i *=0 eller *i *=2, men ibland behövs andra värden) så att den resulterande strängen *uv ⁱ xy ⁱ z*är*inte*på språket*l*. Detta innebär att det bryter mot reglerna som definierar strängar som tillhör språket.

* hur man visar * uv ⁱ xy ⁱ z * är inte i * l *:Detta beror på det specifika språket. Du måste visa att den pumpade strängen bryter mot de definierande egenskaperna för *l *. Vanliga strategier inkluderar:

* visar att strängen nu har ojämlika antal symboler som tidigare var lika. Om * l * till exempel kräver samma antal 'A och' B:er, visar du att pumpning får räkningen att vara ojämlik.

* visar att symbolens ordning nu är felaktig. Till exempel, om * l * kräver att alla "A:er kommer före alla" B, visar du att pumpning kan sätta en "B" före en "A".

* som visar att ett matematiskt samband mellan räkningar inte längre håller. Till exempel, om * l * kräver att antalet "A:er ska vara dubbelt så många B:er, visar du att pumpning bryter mot detta förhållande.

7. Dra slutsatsen att * l * är * inte * kontextfri

Eftersom du har visat att antagandet att * l * är kontextfritt leder till en motsägelse (det pumpande lemmaet måste hålla, men du har visat ett fall där det inte gör det) kan du dra slutsatsen att ditt första antagande var falskt. Därför är * l * inte ett kontextfritt språk.

Exempel:språket l ={a ⁿ b ⁿ c ⁿ | n ≥ 0}

Låt oss bevisa att * l * ={a ⁿ b ⁿ c ⁿ | n ≥ 0} är inte kontextfri med pumpens lemma.

1. antar * l * är kontextfri.

2. Låt * P * vara pumplängden Garanterad av den pumpande lemma.

3. Välj en sträng *S *: Låt*s*=a ^*p* B ^*p* c ^*p* . Det är uppenbart att*s*∈*l*och |*s*| =3*p*≥*p*.

4. Tänk på alla möjliga divisioner * S =Uvxyz * så att | Vxy | ≤ * p * och | vy | ≥ 1: Vi måste överväga var underlagen *V *och *y *kan vara belägna inom *S *. Den avgörande begränsningen är att | vxy | ≤ *p *. Detta begränsar möjligheterna betydligt:

* fall 1:* Vxy * består endast av 'A. Sedan * v * =a ^j och * y * =a ^k För vissa*j*,*k*≥ 0 och*j + k*≥ 1. Om vi ​​pumpar ner (*i*=0) får vi strängen a ^*p-j-k* B ^*p* c ^*p* . Sedan * j + k * ≥ 1 har den här strängen färre än * p * 'a, men har fortfarande * p *' b's och * p * 'c. Därför är det inte i *l *.

* Case 2:* Vxy * består endast av 'B:er. Sedan * v * =b ^j och * y * =b ^k För vissa*j*,*k*≥ 0 och*j + k*≥ 1. Om vi ​​pumpar ner (*i*=0) får vi en ^*p* B ^*p-j-k* c ^*p* . Återigen är antalet 'B:er mindre än *P *, medan antalet' A:er och 'C förblir *P *, så det är inte i *l *.

* Fall 3:* Vxy * består endast av 'c. Sedan * v * =c ^j och * y * =c ^k För vissa*j*,*k*≥ 0 och*j + k*≥ 1. Om vi ​​pumpar ner (*i*=0) får vi en ^*p* B ^*p* c ^*p-j-k* . Antalet c är mindre än *p *, medan antalet 'a och' b är kvar *p *, så det är inte i *l *.

* Case 4:* Vxy * består av 'A och' B's. Sedan | vxy | ≤ *p *, det kan inte inkludera några 'c eftersom alla *p *' a's och *p *'b måste föregå alla' c. Sedan | vy | ≥ 1, minst en av * v * eller * y * måste innehålla en karaktär. Därför * v * =a ^j B ^k och * y * =a ^l B ^m för vissa *j *, *k *, *l *, *m *≥ 0 och *j + k + l + m *≥ 1, med minst en av 'a' eller 'b' i antingen *v *eller *y *.

Om vi ​​pumpar upp (*i*=2) får vi strängen a ^*p+j+l* B ^*p+k+m* c ^*p* . Om * k + m * är noll (så * v * och * y * innehåller bara 'a) antalet' a:s ökar men antalet 'B:s förblir detsamma. Resultatet är en ^*p+j+l* B ^*p* c ^*p* som inte längre är på språket. Om * j + l * är noll (så * v * och * y * innehåller bara 'b), är antalet' B:s ökar men antalet 'A:s förblir detsamma. Resultatet är en ^*p* B ^*p+k+m* c ^*p* som inte längre är på språket. Om båda *k+m *och *j+l *är större än noll, är *uv ² xy ² Z* har fler 'A och' B:er än 'C, vilket betyder att det inte kan vara av formen A ⁿ b ⁿ c ⁿ .

* Fall 5:* Vxy * består av 'B:er och' c. Detta är symmetriskt till fall 4. Återigen, att pumpa upp kommer att resultera i en sträng som inte finns på språket.

5. Motsägelse: I alla möjliga fall har vi visat att det finns en *i *så att *uv ⁱ xy ⁱ z*är inte i*l*. Detta strider mot pumpens lemma.

6. Slutsats: Därför måste vårt första antagande att * l * är kontextfritt vara falskt. Således * l * ={a ⁿ b ⁿ c ⁿ | n ≥ 0} är inte kontextfri.

Nyckeltips för att använda pumpens lemma:

* Förstå lemma exakt: Vet det exakta uttalandet och förhållandena.

* Strategiskt strängval: Valet av * s * är avgörande. Välj en sträng som belyser den egenskap du vill bryta igenom pumpen. Ofta är det att ställa in delar av strängen baserat på * p * till hjälp.

* noggrann fallanalys: Tänk på alla möjliga platser för *V *och *y *inom *S *, med tanke på begränsningarna | Vxy | ≤ * p * och | vy | ≥ 1.

* Välj rätt * i *:Experiment med *i *=0, *i *=2, eller andra värden för att hitta den som tydligt visar kränkningen av *l *. Ibland * i * =0 kommer att få något att försvinna, och * i * =2 kommer att få något att dupliceras.

* var tydlig och rigorös: Förklara exakt varför den pumpade strängen inte längre är i *l *. Se språkets definierande egenskaper.

Pumpande lemma kan vara svårt att behärska. Öva med olika språk för att få erfarenhet av att välja lämpliga strängar och hantera fallanalysen. Kom ihåg att målet är att hitta en sträng där * eventuell * möjlig applicering av pumpens lemma leder till en motsägelse. Lycka till!