Ogdens lemma

I teorin om formella språk är Ogdens lemma (uppkallat efter William F. Ogden) en generalisering av det pumpande lemmat för sammanhangsfria språk .

Påstående

Ogdens lemma — Om ett språk $L$ genereras av en kontextfri grammatik, så finns det några $p\geq 1$ så att $\forall w\in L$ med längd $\geq p$ , och alla sätt att markera $\geq p$ positioner för $w$ som "markerade", det finns en icketerminal $A$ och ett sätt att dela upp $w$ i 5 segment $uxzyv$ , så att

$$S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv$$

$z$ innehåller minst en markerad position.

$xzy$ innehåller högst $p$ markerade positioner.

$u,x$ innehåller båda markerade positioner, eller $y,v$ innehåller båda markerade positioner.

Vi kommer att använda understrykningar för att indikera "markerade" positioner.

Speciella fall

Ogdens lemma anges ofta i följande form, vilket kan erhållas genom att "glömma bort" grammatiken, och koncentrera sig på själva språket: Om ett språk L är sammanhangsfritt, så finns det något tal $p \geq 1$ (där p kan vara en pumplängd eller inte) så att för alla strängar med längd minst p i L och alla sätt att "markera" p eller fler av positionerna i s , kan s skrivas som

$s=uvwxy$

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

1. vx har minst en markerad position,
2. vwx har högst p markerade positioner, och
3. $uv^{n}wx^{n}y\in L$ för alla $n\geq 0$ .

I det speciella fallet där varje position är markerad är Ogdens lemma likvärdigt med det pumpande lemmat för sammanhangsfria språk. Ogdens lemma kan användas för att visa att vissa språk inte är kontextfria i de fall det pumpande lemmat inte är tillräckligt. Ett exempel är språket $\{a^{i}b^{j}c^{k}d^{l}: i=0{\text{ eller }}j=k=l\}$ .

Exempelapplikationer

Icke-sammanhangsfrihet

Det speciella fallet med Ogdens lemma är ofta tillräckligt för att bevisa att vissa språk inte är kontextfria. Till exempel, ${\displaystyle \{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}} är ett standardexempel på icke-$ kontext- fritt språk (, s. 128).

Bevis

Anta att språket genereras av en kontextfri grammatik, låt sedan $p$ vara den längd som krävs i Ogdens lemma, betrakta sedan ordet $a^{p}{ \underline {b^{p}c^{p}}}d^{p}$ på språket. Då kan inte alla de tre villkoren i Ogdens lemma vara uppfyllda.

På liknande sätt kan man bevisa språket "kopiera två gånger" ${\displaystyle L=\{w^{2}|w\in \{a,b\}^{*}\}} är inte kontextfri, genom att använda Ogdens$ lemma på $a^{2p}{\underline {b^{2p}}}a^{2p}b^{2p}$ .

Och det givna exemplet sista avsnittet $\{a^{i}b^{j}c^{k}d^{l} :i=0{\text{ eller }}j=k=l\}$ är inte kontextfri genom att använda Ogdens lemma på $ab^{2p}{\ understryka {c^{2p}}}d^{2p}$ .

Inneboende tvetydighet

Ogdens lemma kan användas för att bevisa den inneboende tvetydigheten hos vissa språk, vilket antyds av titeln på Ogdens artikel.

Exempel : Låt $L_{0}=\{a^{n}b^{m}c^{m}|m,n\geq 1\},L_{1}=\{a^ {m}b^{m}c^{n}|m,n\geq 1\}$ . Språket $L=L_{0}\cup L_{1}$ är i sig tvetydigt. (Exempel från sida 3 i Ogdens tidning.)

Bevis

Låt $p$ vara den pumplängd som behövs för Ogdens lemma, och tillämpa den på meningen $a^{p!+p}{\underline {b^{p}c^{p}}}$ .

Genom rutinkontroll av villkoren för Ogdens lemma finner vi att härledningen är

$$S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv$$

där ${\displaystyle u=a^{p!+p}b ^{psk},x=b^{k},z=b^{s}c^{s'},y=c^{k},v=c^{ps'-k}} ,$ uppfyller $s+s'\geq 1$ och $k\geq 1$ och $p\geq s+s'+2k$ .

Således får vi en härledning av $a^{p!+p}b^{p!+p}c^{p!+p}$ genom att interpolera härledningen med $p!/k$ kopior av $A\Rightarrow ^{*}xAy$ . Enligt denna härledning är en hel undermening $x^{p!/k+1}zy^{p!/k+1}=b^{p!+k+s}c^{p!+k+s'}$ är avkomling av en nod $A$ i härledningsträdet.

Symmetriskt kan vi få en annan härledning av ${\displaystyle a^{p!+p}b^{p!+p}c^{p!+p}} ,$ enligt vilken det finns en hel undermening ${\displaystyle a^{p!+k''+s''}b^{p!+k''+s'''}} är avkomling av en$ nod i härledningsträdet.

Eftersom ${\displaystyle (p!+k+s)+(p!+k''+s''')>2p!+1>p!+p} , de två undermeningarna har icke-tom skärningspunkt, och$ eftersom ingen av dem innehåller den andra, de två härledningsträden är olika.

På liknande sätt är $L^{*}$ i sig tvetydig, och för alla CFG i språket, om vi låter $p$ vara konstanten för Ogdens lemma, finner vi att ${\displaystyle (a^{p!+p}b^{p!+p}c^{p!+p})^{n}} har$ minst ${ \displaystyle 2^{n}}$ olika analyser. Således $L^{*}$ en obegränsad grad av inneboende tvetydighet.

Oavgörbarhet

Beviset kan utvidgas till att visa att det är oavgörbart att avgöra om en CFG i sig är tvetydig, genom att reducera till postkorrespondensproblemet . Det kan också visa att det inte går att avgöra om en CFG har en obegränsad grad av inneboende tvetydighet. (sida 4 i Ogdens tidning)

Konstruktion

Med tanke på alla Post-korrespondensproblem över binära strängar, reducerar vi det till ett beslutsproblem över en CFG.

Givet två valfria listor av binära strängar $\xi _{1},...,\xi _{n}$ och $\eta _{1},...,\eta _{n}$ , skriv om det binära alfabetet till $\{d,e\}$ .

Låt $L\left(\xi _{1},\cdots ,\xi _{n}\right)$ vara språket över alfabetet $\{d,e,f\}$ , genererad av CFG med regler $S\to \xi _{i}Sd^{i}e|f$ för varje $i=1,...,n$ . Definiera ${\displaystyle L\left(\eta _{1},\cdots ,\eta _{n}\right)} på liknande sätt$ .

Nu, med samma argument som ovan, språket $(L_{0}\ cdot L\left(\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n}\right))$ är i sig tvetydig om postkorrespondensproblemet har en lösning.

Och språket $((L_{0}\cdot L\left (\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n} \right)))^{*}$ har en obegränsad grad av inneboende tvetydighet om postkorrespondensproblemet har en lösning.

Generaliserat tillstånd

Bader och Moura har generaliserat lemmat för att tillåta markering av vissa positioner som inte ska inkluderas i vx . Deras beroende av parametrarna förbättrades senare av Dömösi och Kudlek. Om vi ​​betecknar antalet sådana exkluderade positioner med $d\geq p(e+1)$ måste antalet d markerade positioner som vi vill inkludera några i vx uppfylla ) , där p är någon konstant som bara beror på språket. Påståendet blir att varje s kan skrivas som

$s=uvwxy$

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

1. vx har minst en markerad position och ingen exkluderad position,
2. vwx har högst $p^{(e+1)}$ markerade positioner, och
3. $uv^{n}wx^{n}y\in L$ för alla $n\geq 0$ .

Dessutom har antingen var och en av u,v,w en markerad position, eller var och en av $w,x,y$ har en markerad position.