Pumping Lemma för vanliga språk är ett kraftfullt verktyg för att bevisa att ett språk är * inte * regelbundet. Det fungerar genom motsägelse:du antar att språket * är * regelbundet och visar sedan att detta antagande leder till en motsägelse av själva lemma. Så här fungerar det:
1. Pumping Lemma -uttalandet:
Pumpens lemma säger att för alla regelbundna språk l finns det en pumplängd P så att alla strängar i L med längd | W | ≥ P kan delas upp i tre underlag, W =XYZ, tillfredsställer följande villkor:
* | XY | ≤ P: Längden på sammankopplingen av x och y är mindre än eller lika med p.
* | y |> 0: Underlaget är inte tom.
* för alla i ≥ 0, xy
i
z ∈ L: Pumpning av noll eller fler gånger (inklusive att ta bort det helt när i =0) resulterar i en sträng som fortfarande finns på språket L.
2. Bevisstrategi:
Följ dessa steg för att bevisa att ett språk l inte är regelbundet med hjälp av pumpens lemma:
* Antag att L är regelbundet: Börja med att anta, för motsägelse, att l är ett regelbundet språk.
* Välj en pumplängd P: Pumpens lemma garanterar förekomsten av en pumplängd P; Du behöver inte hitta dess faktiska värde, bara hänvisa till det som 'p'.
* Välj en sträng w ∈ L så att | w | ≥ P: Välj försiktigt en sträng W från språket L vars längd är åtminstone p. Valet av W är avgörande; Det måste låta dig skapa en motsägelse i nästa steg. Detta involverar ofta strängar med en specifik struktur relaterad till språkets definition.
* Visa att ingen nedbrytning w =xyz uppfyller pumpens lemma -förhållanden: Detta är bevisets hjärta. För * eventuell * möjlig nedbrytning av W till XYZ tillfredsställande | XY | ≤ p och | y |> 0, du måste visa att det finns några i ≥ 0 så att xy
i
Z ∉ L. Detta innebär att pumpa Y bryter mot definitionen av språket L. Ofta demonstrerar du detta genom att visa att pumpa Y antingen kommer att:
* introducera en obalans: Ändra antalet förekomster för någon symbol, vilket bryter mot en räkningsbegränsning i L.
* Skapa en ogiltig struktur: Bryt mönstret eller strukturen som krävs enligt L:s definition.
* introducera en ogiltig underlag: Skapa en underlag som inte tillhör språket.
* drar slutsatsen att L inte är regelbunden: Eftersom du har visat att ingen sådan nedbrytning kan existera för den valda strängen W, motsäger detta pumpande lemma. Därför måste det första antagandet att L är regelbundet vara falskt och L är inte regelbundet.
Exempel:Proving {a
n
b
n
| n ≥ 0} är inte regelbundet:
Låt l ={a
n
b
n
| n ≥ 0}.
1. Antag att L är regelbunden.
2. Välj P: Låt P vara pumplängden.
3. Välj W: Låt W =A
p
B
p
. Det är uppenbart att w ∈ L och | W | ≥ p.
4. Visa ingen nedbrytning uppfyller förhållandena: Låt oss överväga alla nedbrytningar w =xyz så att | xy | ≤ p och | y |> 0. Sedan | XY | ≤ p, y måste bestå * endast * av A:er (eftersom y är en underlag från de första P -tecken). Således, y =a
k
För vissa k> 0. Pump y noll gånger:xy
0
z =a
p-k
B
p
. Den här strängen är inte i L eftersom antalet A och B är olika. Detta strider mot pumpens lemma.
5. Slutsats: Eftersom vi har nått en motsägelse måste vårt antagande att L är regelbundet vara falskt. Därför l ={a
n
b
n
| n ≥ 0} är inte ett vanligt språk.
Nyckeln är att noggrant välja strängen "w" och på ett smart sätt analysera alla möjliga nedbrytningar "xyz" för att visa att pumpning "y" alltid leder till en sträng utanför språket. Ju mer komplexa språket, desto mer komplicerat blir valet av `w` och analysen.
