Vækst Lemma

Det pumpende lemma ( vækstlemma , pumpende lemma ; engelsk pumping lemma ) er en vigtig påstand om automatteori , der i mange tilfælde gør det muligt at kontrollere , om et givet sprog er automatiseret . Da alle finite sprog er automater, giver det mening kun at udføre denne kontrol for uendelige sprog. Udtrykket "pumpning" i titlen på lemmaet afspejler muligheden for gentagen gentagelse af en delstreng i en hvilken som helst streng af passende længde i ethvert uendeligt automatsprog.

Der er også et vækstlemma for kontekstfrie sprog , et endnu mere generelt udsagn er vækstlemmaet for indekssprog .

Ordlyd

For et uendeligt automatsprog over et alfabet eksisterer der et naturligt tal , sådan at der for ethvert ord af længde i det mindste er ord sådan, at , , og for hvert ikke-negativt heltal er strengen et ord i sproget . $L$ $V$ $n$ $\alpha \i L$ $n$ $u,v,w\in V^{*}$ $\alpha =uvw$ $|uv|\leqslant n$ $|v|\geqslant 1$ $jeg$ $uv^{i}w$ $L$

Notation i kvantifikatorer:

(\eksisterer n\i \mathbb {N} )(\forall \alpha \i L:|\alpha |\geqslant n)(\eksisterer u,v,w\i V^{*}):\ ,[\alpha =uvw\land |uv|\leqslant n\land |v|\geqslant 1\land (\forall i\in \mathbb {N} \cup \{0\},uv^{i}w\ i L)]

Bevis

Lad et automatsprog indeholde et uendeligt antal kæder og antag, at det genkendes af en deterministisk finit automat med tilstande . For at kontrollere konklusionen på lemmaet vælger vi en vilkårlig kæde af dette sprog, der har længde . $L$ $L$ $EN$ $n$ $\alfa$ $n$

Hvis den endelige automat genkender , så er kæden tilladt af denne automat, det vil sige, i automaten er der en længdevej fra initial til en af sluttilstandene, markeret med kædesymboler . Denne vej kan ikke være enkel, den skal passere nøjagtigt gennem tilstanden, mens automaten har tilstande. Dette betyder, at denne sti passerer mindst to gange gennem den samme tilstand af automaten , det vil sige, at der er en cyklus med en gentagelsestilstand på denne sti. Lad dette være en gentagelsestilstand . $EN$ $L$ $\alfa$ $EN$ $n$ $\alfa$ $n+1$ $EN$ $n$ $EN$ $q_{k}$

Lad os opdele kæden i tre dele, så , hvor er underkæden, der overføres fra staten tilbage til staten , og er underkæden, der overføres fra tilstanden til den endelige tilstand. Bemærk, at både og kan være tomme, men understrengen kan ikke være tom. Men så er det indlysende, at automaten også skal tillade kæden , da den gentagne delstreng igen følger den cykliske vej fra til , såvel som kæden og enhver af formen . $\alfa$ $\alpha=uvw$ $v$ $EN$ $q_{k}$ $q_{k}$ $w$ $EN$ $q_{k}$ $u$ $w$ $v$ $EN$ $uvvw$ $v$ $q_{k}$ $q_{k}$ $uvvvw$ $uvv...vw$

Dette ræsonnement udgør beviset for det pumpende lemma.

Omvendt formulering

En anden form for dette lemma, som nogle gange er mere praktisk at anvende for at bevise, at et bestemt sprog er ikke-automatisk, for et sprog over et alfabet er som følger - hvis sagen holder: $L$ $V$

(\forall n\in \mathbb {N} )(\eksisterer \alpha \i L\colon |\alpha |\geqslant n)(\forall u,v,w\in V^{*}\colon \alpha =uvw\land |v|\geqslant 1\ \land |uv|\leqslant n)(\eksisterer i\i \mathbb {N} \cup \{0\})uv^{i}w\ikke \ i L

så er sproget ikke-automatisk. $L$

For at bevise, at et sprog er ikke-automatisk, kan man også bruge det faktum, at skæringspunktet mellem regulære sprog er regulært. Det er således problematisk direkte at anvende det pumpende lemma på sproget af regulære parentesstrukturer i alfabetet , men dets skæring med sproget giver sproget , hvis ikke-automatik trivielt følger af det pumpende lemma. $\{(,)\}$ $(^{*})^{*}$ $(^{n})^{n}$

Litteratur

John Hopcroft , Rajiv Motwani , Jeffrey Ullman . Introduktion til automatteori, sprog og beregning. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .

Vækst Lemma

Ordlyd

Bevis

Omvendt formulering

Litteratur

Links