Čerpání lemmatu pro běžné jazyky - Pumping lemma for regular languages

V teorii formální jazyky, čerpání lemmatu pro běžné jazyky je lemma který popisuje základní vlastnost všech běžné jazyky. Neformálně se říká, že všechna dostatečně dlouhá slova v běžném jazyce mohou být čerpáno- to znamená nechat střední část slova libovolně často opakovat - a vytvořit tak nové slovo, které také leží ve stejném jazyce.

Konkrétně čerpací lemma říká, že pro každý běžný jazyk ${ displaystyle L}$ existuje konstanta ${ displaystyle p}$ takové, že každé slovo ${ displaystyle w}$ v ${ displaystyle L}$ alespoň s délkou ${ displaystyle p}$ lze rozdělit na tři podřetězce, ${ displaystyle w = xyz}$, kde je střední část ${ displaystyle y}$ nesmí být prázdné, takže slova ${ displaystyle xz, xyz, xyyz, xyyyz, ...}$ vytvořeno opakováním ${ displaystyle y}$ nula nebo vícekrát je stále v ${ displaystyle L}$. Tento proces opakování se nazývá „čerpání“. Čerpací lemma navíc zaručuje, že délka ${ displaystyle xy}$ bude nanejvýš ${ displaystyle p}$, kterým se stanoví omezení způsobů, jakými ${ displaystyle w}$ mohou být rozděleny. Konečné jazyky vakuově uspokojit čerpací lemma tím, že ${ displaystyle p}$ rovná maximální délce řetězce v ${ displaystyle L}$ plus jedna.

Pumpovací lemma je užitečné pro vyvrácení pravidelnosti konkrétního dotyčného jazyka. Poprvé to prokázal Michael Rabin a Dana Scott v roce 1959,^[1] a znovu objeven krátce poté Yehoshua Bar-Hillel, Micha A. Perles, a Eli Shamir v roce 1961, jako jejich zjednodušení čerpání lemmatu pro bezkontextové jazyky.^[2][3]

Formální prohlášení

Nechat ${ displaystyle L}$ být běžným jazykem. Pak existuje celé číslo ${ displaystyle p geq 1}$ záleží jen na ${ displaystyle L}$ tak, že každý řetězec ${ displaystyle w}$ v ${ displaystyle L}$ alespoň délky ${ displaystyle p}$ (${ displaystyle p}$ se nazývá „čerpací délka“^[4]) lze psát jako ${ displaystyle w = xyz}$ (tj., ${ displaystyle w}$ lze rozdělit na tři podřetězce), splňující následující podmínky:

• ${ displaystyle | y | geq 1}$
• ${ displaystyle | xy | leq p}$
• ${ displaystyle ( forall n geq 0) (xy ^ {n} z v L)}$

${ displaystyle y}$ je podřetězec, který lze čerpat (odebrat nebo opakovat libovolněkrát a výsledný řetězec je vždy v ${ displaystyle L}$). (1) znamená smyčku ${ displaystyle y}$ k čerpání musí mít délku alespoň jednu; (2) znamená, že k smyčce musí dojít během první ${ displaystyle p}$ postavy. ${ displaystyle | x |}$ musí být menší než ${ displaystyle p}$ (závěr bodů (1) a (2)), ale kromě toho neexistuje žádné omezení ${ displaystyle x}$ a ${ displaystyle z}$.

Jednoduše řečeno, pro každý běžný jazyk ${ displaystyle L}$, jakékoli dostatečně dlouhé slovo ${ displaystyle w}$ (v ${ displaystyle L}$) lze rozdělit na 3 části. tj. ${ displaystyle w = xyz}$ , tak, že všechny řetězce ${ displaystyle xy ^ {n} z}$ pro ${ displaystyle n geq 0}$ jsou také v ${ displaystyle L}$.

Níže je formální vyjádření Pumping Lemma.

${ displaystyle { begin {array} {l} ( forall L subseteq Sigma ^ {*}) quad ({ mbox {regular}} (L) Rightarrow quad (( existuje p geq 1) (( forall w in L) ((| w | geq p) Rightarrow quad (( existuje x, y, z in Sigma ^ {*}) (w = xyz land (| y | geq 1 land | xy | leq p land ( forall n geq 0) (xy ^ {n} z v L)))))))))) end {pole }}}$

Použití lemmatu

Čerpací lemma se často používá k prokázání nepravidelnosti konkrétního jazyka: a důkaz rozporem (pravidelnosti jazyka) může sestávat z vystavení slova (požadované délky) v jazyce, kterému chybí vlastnost uvedená v čerpacím lemmatu.

Například jazyk ${ displaystyle L = {a ^ {n} b ^ {n}: n geq 0 }}$ přes abecedu ${ displaystyle Sigma = {a, b }}$ lze ukázat jako nepravidelné následovně:

Nechat ${ displaystyle w, x, y, z, p}$, a ${ displaystyle n}$ být používán v formální prohlášení pro čerpací lemma výše. Předpokládáme, že existuje nějaká konstanta ${ displaystyle p}$. Nechat ${ displaystyle w}$ v ${ displaystyle L}$ být dán ${ displaystyle w = a ^ {p} b ^ {p}}$, což je řetězec delší než ${ displaystyle p}$. U čerpacího lemmatu musí dojít k určitému rozkladu ${ displaystyle w = xyz}$ s ${ displaystyle | xy | leq p}$ a ${ displaystyle | y | geq 1}$ takhle${ displaystyle xy ^ {i} z}$ v ${ displaystyle L}$ pro každého ${ displaystyle i geq 0}$. Použitím ${ displaystyle | xy | leq p}$, víme ${ displaystyle y}$ sestává pouze z instancí ${ displaystyle a}$. Navíc, protože ${ displaystyle | y | geq 1}$, obsahuje alespoň jednu instanci dopisu ${ displaystyle a}$. Nyní pumpujeme ${ displaystyle y}$ nahoru: ${ displaystyle xy ^ {2} z}$ má více instancí dopisu ${ displaystyle a}$ než dopis ${ displaystyle b}$, protože jsme přidali několik instancí ${ displaystyle a}$ bez přidání instancí ${ displaystyle b}$. Proto, ${ displaystyle xy ^ {2} z}$ není v ${ displaystyle L}$. Došli jsme k rozporu. Proto se předpokládá, že ${ displaystyle L}$ je pravidelný (tj. existuje takový ${ displaystyle p}$) musí být nesprávné. Proto ${ displaystyle L}$ není pravidelné.

Důkaz, že jazyk vyvážených (tj. správně vnořených) závorek není pravidelné, sleduje stejnou myšlenku. Dáno ${ displaystyle p}$, existuje řetězec vyvážených závorek, který začíná více než ${ displaystyle p}$ levé závorky, takže ${ displaystyle y}$ bude sestávat výhradně z levé závorky. Opakováním ${ displaystyle y}$, můžeme vytvořit řetězec, který neobsahuje stejný počet levé a pravé závorky, a proto je nelze vyvážit.

Důkaz čerpacího lemmatu

Důkaz: Kdykoli dostatečně dlouhý tětiva xyz je rozpoznán a konečný automat, muselo to dosáhnout nějakého stavu (${ displaystyle q_ {s} = q_ {t}}$) dvakrát. Proto po opakování („pumpování“) střední části ${ displaystyle y}$ libovolně často (xyyz, xyyyz, ...) slovo bude stále rozpoznáno.

Pro každý běžný jazyk existuje a konečný stavový automat (FSA), který jazyk přijímá. Počet států v takovém FSA se počítá a tento počet se použije jako čerpací délka ${ displaystyle p}$. Minimálně pro řetězec délky ${ displaystyle p}$, nechť ${ displaystyle q_ {0}}$ být počátečním stavem a nechat ${ displaystyle q_ {1}, ..., q_ {p}}$ být posloupností dalšího ${ displaystyle p}$ státy navštívené jako řetězec je emitován. Protože FSA má jen ${ displaystyle p}$ státy, v této posloupnosti ${ displaystyle p + 1}$ navštívené státy musí existovat alespoň jeden stát, který se opakuje. Psát si ${ displaystyle q_ {s}}$ za takový stav. Přechody, které berou stroj z prvního setkání stavu ${ displaystyle q_ {s}}$ k druhému státnímu střetnutí ${ displaystyle q_ {s}}$ přiřadit nějaký řetězec. Tento řetězec se nazývá ${ displaystyle y}$ v lematu a protože stroj bude odpovídat řetězci bez ${ displaystyle y}$ porcí nebo s provázkem ${ displaystyle y}$ při libovolném počtu opakování jsou podmínky lemmatu splněny.

Například následující obrázek ukazuje FSA.

FSA přijímá řetězec: abeceda. Vzhledem k tomu, že tento řetězec má délku alespoň stejně velkou jako počet států, což jsou čtyři, znak princip pigeonhole označuje, že mezi počátečním stavem a dalšími čtyřmi navštívenými státy musí být alespoň jeden opakovaný stav. V tomto příkladu pouze ${ displaystyle q_ {1}}$ je opakovaný stav. Od podřetězce před naším letopočtem provede stroj přechody, které začínají ve stavu ${ displaystyle q_ {1}}$ a končí ve stavu ${ displaystyle q_ {1}}$, tato část mohla být opakována a FSA by to stále přijal, dal řetězec abcbcd. Případně před naším letopočtem část mohla být odstraněna a FSA by stále souhlasil s poskytnutím řetězce inzerát. Pokud jde o čerpací lemma, řetězec abeceda je rozbit na ${ displaystyle x}$ část A, a ${ displaystyle y}$ část před naším letopočtem a a ${ displaystyle z}$ část d.

Obecná verze čerpání lemmatu pro běžné jazyky

Pokud jazyk ${ displaystyle L}$ je normální, pak existuje číslo ${ displaystyle p geq 1}$ (čerpací délka) taková, že každý řetězec ${ displaystyle uwv}$ v ${ displaystyle L}$ s ${ displaystyle | w | geq p}$ lze napsat ve formě

${ displaystyle uwv = uxyzv}$

s provázky ${ displaystyle x}$, ${ displaystyle y}$ a ${ displaystyle z}$ takhle ${ displaystyle | xy | leq p}$, ${ displaystyle | y | geq 1}$ a

${ displaystyle uxy ^ {i} zv}$ je v ${ displaystyle L}$ pro každé celé číslo ${ displaystyle i geq 0}$.^[5]

Z toho je výše standardní verze následuje speciální případ, s oběma ${ displaystyle u}$ a ${ displaystyle v}$ je prázdný řetězec.

Jelikož obecná verze klade na jazyk přísnější požadavky, lze ji použít k prokázání nepravidelnosti mnoha dalších jazyků, například ${ displaystyle {a ^ {m} b ^ {n} c ^ {n}: m geq 1 { text {a}} n geq 1 }}$.^[6]

Konverze lemmatu není pravdivá

Zatímco čerpací lemma uvádí, že všechny běžné jazyky splňují podmínky popsané výše, obrácení tohoto tvrzení není pravdivé: jazyk, který splňuje tyto podmínky, může být i nadále nepravidelný. Jinými slovy, jak původní, tak obecná verze čerpacího lemmatu dávají a nutné ale ne dostatečný stav aby byl jazyk pravidelný.

Zvažte například následující jazyk:

${ displaystyle { begin {matrix} L & = & {uvwxy: u, y in {0,1,2,3 } ^ {*}; v, w, x in {0,1, 2,3 } land (v = w lor v = x lor x = w) } && cup {w: w in {0,1,2,3 } ^ { *} land { text {přesně}} { tfrac {1} {7}} { text {znaků}} w { text {jsou 3's}} } end {matrix}}}$.

Jinými slovy, ${ displaystyle L}$ obsahuje všechny řetězce nad abecedou ${ displaystyle {0,1,2,3 }}$ s podřetězcem délky 3 včetně duplicitního znaku, stejně jako všechny řetězce nad touto abecedou, kde přesně 1/7 znaků řetězce jsou 3. Tento jazyk není běžný, ale stále jej lze „pumpovat“ ${ displaystyle p = 5}$. Předpokládejme nějaký řetězec s má délku alespoň 5. Poté, co má abeceda pouze čtyři znaky, musí být alespoň dva z prvních pěti znaků v řetězci duplikáty. Jsou odděleny nejvýše třemi znaky.

• Pokud jsou duplicitní znaky odděleny 0 znaky nebo 1, načerpejte jeden z dalších dvou znaků v řetězci, což neovlivní podřetězec obsahující duplikáty.
• Pokud jsou duplicitní znaky odděleny 2 nebo 3 znaky, oddělte je dvěma znaky. Při čerpání dolů nebo nahoru se vytvoří podřetězec o velikosti 3, který obsahuje 2 duplicitní znaky.
• Druhá podmínka ${ displaystyle L}$ zajišťuje to ${ displaystyle L}$ není pravidelné: Zvažte řetězec ${ displaystyle (013) ^ {3m} (012) ^ {i}}$. Tento řetězec je v ${ displaystyle L}$ přesně kdy ${ displaystyle i = 4m}$ a tudíž ${ displaystyle L}$ není pravidelná Věta Myhill – Nerode.

The Věta Myhill – Nerode poskytuje test, který přesně charakterizuje běžné jazyky. Typickou metodou pro prokázání, že jazyk je pravidelný, je konstrukce buď a konečný stavový stroj nebo a regulární výraz pro jazyk.

Viz také

• Čerpání lemmatu pro bezkontextové jazyky
• Ogdenovo lemma

Poznámky

Reference

• Lawson, Mark V. (2004). Konečné automaty. Chapman and Hall / CRC. ISBN  978-1-58488-255-8. Zbl  1086.68074.
• Sipser, Michael (1997). „1.4: Nepravidelné jazyky“. Úvod do teorie výpočtu. PWS Publishing. str.77–83. ISBN  978-0-534-94728-6. Zbl  1169.68300.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu. Reading, Massachusetts: Addison-Wesley Publishing. ISBN  978-0-201-02988-8. Zbl  0426.68001. (Viz kapitola 3.)
• Bakhadyr Khoussainov; Anil Nerode (6. prosince 2012). Teorie automatů a její aplikace. Springer Science & Business Media. ISBN  978-1-4612-0171-7.