Růstové lemma

Pumpovací lemma ( růstové lemma , pumping lemma ; anglicky pumping lemma ) je důležitým tvrzením teorie automatů , které v mnoha případech umožňuje ověřit, zda je daný jazyk automat . Protože všechny konečné jazyky jsou automaty, má smysl provádět tuto kontrolu pouze pro nekonečné jazyky. Výraz „pumpování“ v názvu lemmatu odráží možnost opakovaného opakování nějakého podřetězce v libovolném řetězci vhodné délky v libovolném jazyce nekonečného automatu.

Existuje také růstové lemma pro bezkontextové jazyky , ještě obecnější tvrzení je růstové lemma pro indexové jazyky .

Formulace

Pro jazyk nekonečného automatu nad abecedou existuje přirozené číslo , takže pro každé slovo délky alespoň existují slova taková, že , a pro každé nezáporné celé číslo je řetězec slovem jazyka . $L$ $PROTI$ $n$ $\alpha \in L$ $n$ $u,v,w\in V^{*}$ $\alpha =uvw$ $|uv|\leqslant n$ $|v|\geqslant 1$ $i$ $uv^{i}w$ $L$

Zápis v kvantifikátorech:

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

Důkaz

Nechť jazyk automatu obsahuje nekonečný počet řetězců a předpokládejme, že je rozpoznán deterministickým konečným automatem se stavy . Pro kontrolu závěru lemmatu zvolíme libovolný řetězec tohoto jazyka, který má délku . $L$ $L$ $A$ $n$ $\alpha$ $n$

Pokud konečný automat rozpozná , pak je řetězec tímto automatem povolen, to znamená, že v automatu existuje cesta délky od počátečního do jednoho z koncových stavů, označená symboly řetězce . Tato cesta nemůže být jednoduchá, musí procházet přesně stavem, kdežto automat stavy má . To znamená, že tato cesta prochází alespoň dvakrát stejným stavem automatu , to znamená, že na této cestě je cyklus s opakujícím se stavem. Nechť je to opakující se stav . $A$ $L$ $\alpha$ $A$ $n$ $\alpha$ $n+1$ $A$ $n$ $A$ $q_{k}$

Rozdělme řetězec na tři části, takže , kde je podřetězec, který přechází ze stavu zpět do stavu , a je podřetězec, který přechází ze stavu do konečného stavu. Všimněte si, že obojí a může být prázdné, ale podřetězec nemůže být prázdný. Pak je ale zřejmé, že automat musí povolit i řetězec , protože opakovaný podřetězec opět sleduje cyklickou cestu od do , stejně jako řetězec a jakýkoli tvar . $\alpha$ $\alpha=uvw$ $proti$ $A$ $q_{k}$ $q_{k}$ $w$ $A$ $q_{k}$ $u$ $w$ $proti$ $A$ $uvvw$ $proti$ $q_{k}$ $q_{k}$ $uvvvw$ $uvv...vw$

Tato úvaha představuje důkaz čerpacího lemmatu.

Opačná formulace

Další forma tohoto lemmatu, kterou je někdy vhodnější použít k prokázání, že určitý jazyk je neautomatický, pro jazyk nad abecedou je následující – pokud platí: $L$ $PROTI$

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

pak je jazyk neautomatický. $L$

K prokázání, že jazyk je neautomatický, lze také použít skutečnost, že průnik regulárních jazyků je pravidelný. Je tedy problematické přímo aplikovat pumpovací lemma na jazyk pravidelných závorkových struktur v abecedě , ale jeho průnik s jazykem dává jazyk , jehož neautomatickost triviálně vyplývá z pumpovacího lemmatu. $\{(,)\}$ $(^{*})^{*}$ $(^{n})^{n}$

Literatura

John Hopcroft , Rajiv Motwani , Jeffrey Ullman . Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .

Odkazy

Formální jazyky a gramatiky
Pentus, A. E., Pentus, M. R. Teorie formálních jazyků. Studijní příručka . M., 2004
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků - M.: MZ-Press, 2006, 2. vyd. — ISBN 5-94073-094-9
Vinokurov N.S. Složitost některých přirozených problémů ve strukturách automatů // Sib. matematika. časopis, 2005, ročník 46, č. 1. (nepřístupný odkaz od 13.05.2013 [3456 dní] - historie )