Pumpande lemma för sammanhangsfria språk

Inom datavetenskap , särskilt inom formell språkteori , är pumplemmat . för kontextfria språk , även känt som Bar-Hillel- lemmat , ett lemma som ger en egenskap som delas av alla sammanhangsfria språk och generaliserar det pumpande lemmat för vanliga språk språk .

Det pumpande lemmat kan användas för att konstruera ett motsägelsefullt bevis på att ett specifikt språk inte är kontextfritt. Omvänt räcker inte det pumpande lemmat för att garantera att ett språk är kontextfritt; det finns andra nödvändiga villkor, som Ogdens lemma eller Interchange-lemmat .

Formellt uttalande

Bevisidé: Om $s$ är tillräckligt lång, måste dess härledningsträd i form av en Chomsky-normalformsgrammatik innehålla något icke-terminalt $N$ två gånger på någon trädväg (övre bilden). Genom att upprepa $n$ gånger härledningsdelen $N$ ⇒...⇒ $vNx$ erhålls en härledning för $uv^{n}wx ^{n}y$ (nedre vänstra och högra bilden för $n=0$ respektive $2$ ).

Om ett språk $L$ är kontextfritt, så finns det något heltal $p\geq 1$ (kallad "pumplängd") så att varje sträng $s$ i $L$ som har en längd på $p$ eller fler symboler (dvs. med $|s|\geq p$ ) kan skrivas som

$s=uvwxy$

med delsträngar $u,v,w,x$ och $y$ , så att

1. $|vx|\geq 1$ ,

2. $|vwx|\leq p$ , och

3. $uv^{n}wx^{n}y\in L$ för alla $n\geq 0$ .

Nedan är ett formellt uttryck för Pumping Lemma.

$_ \displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{kontextfri}}(L)\Högerpil \\\quad ((\exists p\geq 1)((\forall s\in L)((|s|\geq p)\Högerpil \\\quad ((\finns u,v,w,x,y\i \Sigma ^{*} )(s=uvwxy\land |vx|\geq 1\land |vwx|\leq p\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))) )))\end{array}}}$

Informellt uttalande och förklaring

Det pumpande lemmat för sammanhangsfria språk (kallas bara "the pumping lemma" för resten av denna artikel) beskriver en egenskap som alla sammanhangsfria språk garanterat har.

Egenskapen är en egenskap för alla strängar i språket som är av minst $p$ , där $p$ är en konstant – kallad pumplängd – som varierar mellan sammanhangsfria språk.

Säg att $s$ är en sträng med minst längden $p$ som finns i språket.

Det pumpande lemma anger att $s$ kan delas upp i fem delsträngar, $s=uvwxy$ , där $vx$ är icke-tom och längden på $vwx$ är som mest $p$ , så att $v$ och ${\displaystyle x} upprepas$ lika många gånger ( ${\displaystyle n})$ i ${\ displaystyle s}$ producerar en sträng som fortfarande finns i språket. Det är ofta användbart att upprepa noll gånger, vilket tar bort $v$ och $x$ från strängen. Denna process att "pumpa upp" $s$ med ytterligare kopior av $v$ och $x$ är det som ger pumplemmat dess namn.

Finita språk (som är regelbundna och därmed kontextfria) lyder det pumpande lemma trivialt genom att ha $p$ lika med den maximala stränglängden i $L$ plus ett. Eftersom det inte finns några strängar av denna längd bryts inte pumplemmat.

Användning av lemma

Det pumpande lemma används ofta för att bevisa att ett givet språk L är icke-kontextfritt, genom att visa att godtyckligt långa strängar s finns i L som inte kan "pumpas" utan att producera strängar utanför L .

Till exempel, om $S\subset \mathbb {N}$ är oändlig men inte innehåller en (oändlig) aritmetisk progression , då $L=\{ a^{n}:n\in S\}$ är inte kontextfri. I synnerhet är varken primtalen eller kvadrattalen kontextfria.

Till exempel språket $L=\{a^{n}b^{n}c^{n}|n>0\}$ kan visas vara icke-kontextfri genom att använda pumplemmat i ett bevis genom motsägelse . Antag först att L är kontextfri. Genom pumplemmat finns det ett heltal p som är pumplängden för språket L . Betrakta strängen $s=a^{p}b^{p}c^{p}$ i L . Det pumpande lemmat talar om för oss att s kan skrivas på formen $s=uvwxy$ , där u, v, w, x och y är delsträngar, så att $|vx|\geq 1$ , $|vwx|\leq p$ , och $uv^{i}wx^{i}y\in L$ för varje heltal $i \geq 0$ . Genom valet av s och det faktum att $|vwx|\leq p$ , det är lätt att se att delsträngen vwx inte kan innehålla fler än två distinkta symboler. Det vill säga, vi har en av fem möjligheter för vwx :

1. $vwx=a^{j}$ för vissa $j\leq p$ .
2. $vwx=a^{j}b^{k}$ för vissa j och k med $j+k\leq p$
3. $vwx=b^{j}$ för vissa $j\leq p$ .
4. $vwx=b^{j}c^{k}$ för vissa j och k med $j+k\leq p$ .
5. $vwx=c^{j}$ för vissa $j\leq p$ .

För varje fall kan det enkelt verifieras att $uv^{i}wx^{i}y$ inte innehåller lika många av varje bokstav för någon $i\neq 1$ . Således $uv^{2}wx^{2}y$ inte formen $a^{i}b^{i}c^ {i}$ . Detta strider mot definitionen av L . Därför måste vårt initiala antagande att L är kontextfri vara falskt.

Medan det pumpande lemmat ofta är ett användbart verktyg för att bevisa att ett givet språk inte är kontextfritt, ger det inte en fullständig karaktärisering av de kontextfria språken. Om ett språk inte uppfyller det villkor som pumplemmat ger har vi konstaterat att det inte är kontextfritt. Å andra sidan finns det språk som inte är kontextfria, men som ändå uppfyller villkoret som pumplemmat ger, t.ex.

$L=\{b^{j}c^{k}d^{l}|j,k,l\in \mathbb {N} \}\cup \ {a^{i}b^{j}c^{j}d^{j}|i,j\in \mathbb {N} ,i\geq 1\}$

för s = b ^j c ^k d ^l med t.ex. j ≥1 välj vwx att endast bestå av b s, för s = a ⁱ b ^j c ^j d ^j välj vwx att endast bestå av a s; i båda fallen är alla pumpade strängar fortfarande i L .

En föregångare till pumplemma användes 1960 av Scheinberg för att bevisa att ${\displaystyle L=\{a^{n}b^{n}a^{n}|n>0\}} är inte kontextfri$ .

• Bar-Hillel, Y .; Micha Perles ; Eli Shamir (1961). "Om formella egenskaper hos enkla frasstrukturgrammatiker". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung . 14 (2): 143–172. — Omtryckt i:    Y. Bar-Hillel (1964). Språk och information: Utvalda uppsatser om deras teori och tillämpning . Addison-Wesley-serien i logik. Addison-Wesley. s. 116–150. ISBN 0201003732 . OCLC 783543642 .
•   Michael Sipser (1997). Introduktion till teorin om beräkning . PWS Publishing. ISBN 0-534-94728-X . Avsnitt 1.4: Nonregular Languages, s. 77–83. Avsnitt 2.3: Icke-kontextfria språk, s. 115–119.