Lemă de pompare pentru limbi obișnuite

În teoria limbajelor formale , lema de pompare pentru limbile obișnuite este o condiție necesară pentru ca o limbă să fie regulată . Este folosit pentru a demonstra că o limbă aparține unei clase de limbaje formale diferite de cea generată de gramaticile formale de tip 3.

Definiție formală

Este ${\mathcal {A}}=\left\langle \Sigma ,Q,\delta ,s_{0},F\right\rangle$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, Q, \ delta, s_ {0}, F \ right \ rangle}$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, Q, \ delta, s_ {0}, F \ right \ rangle}$ un automat cu stare finită astfel încât $|Q|=n$ ${\ displaystyle | Q | = n}$ ${\ displaystyle | Q | = n}$ , este $L(A)$ ${\ displaystyle L (A)}$ ${\ displaystyle L (A)}$ limbajul recunoscut de automat și ambele $z\in L(A)$ ${\ displaystyle z \ în L (A)}$ ${\ displaystyle z \ în L (A)}$ astfel încât $|z|\geq n$ ${\ displaystyle | z | \ geq n}$ ${\ displaystyle | z | \ geq n}$ ,

Apoi puteți scrie $z=uvw$ ${\ displaystyle z = uvw}$ ${\ displaystyle z = uvw}$ cu $|uv|\leq n$ ${\ displaystyle | uv | \ leq n}$ ${\ displaystyle | uv | \ leq n}$ Și $v\neq \epsilon$ ${\ displaystyle v \ neq \ epsilon}$ ${\ displaystyle v \ neq \ epsilon}$ prin urmare $uv^{*}w\in L(A)$ ${\ displaystyle uv ^ {*} w \ în L (A)}$ ${\ displaystyle uv ^ {*} w \ în L (A)}$ .

Demonstrație

Este $z=x_{1}x_{2}\cdots x_{k}\in L(A)$ ${\ displaystyle z = x_ {1} x_ {2} \ cdots x_ {k} \ în L (A)}$ ${\ displaystyle z = x_ {1} x_ {2} \ cdots x_ {k} \ în L (A)}$ . Atâta timp cât $|z|\geq n$ ${\ displaystyle | z | \ geq n}$ ${\ displaystyle | z | \ geq n}$ pentru a accepta șirul z pe care trebuie să îl asume automatul $n+1$ ${\ displaystyle n + 1}$ $n + 1$ (inclusiv cea inițială), dar din moment ce automatul are exact n stări distincte, prin principiul sertarului , una dintre stările $\left\{q_{z}0,q_{z}1,q_{z}2,\cdots ,q_{z}k\right\}$ ${\ displaystyle \ left \ {q_ {z} 0, q_ {z} 1, q_ {z} 2, \ cdots, q_ {z} k \ right \}}$ ${\ displaystyle \ left \ {q_ {z} 0, q_ {z} 1, q_ {z} 2, \ cdots, q_ {z} k \ right \}}$ (unde este $q_{z}k$ ${\ displaystyle q_ {z} k}$ ${\ displaystyle q_ {z} k}$ este starea finală în care este recunoscut cuvântul) trebuie să apară cel puțin de două ori.

Asuma ca $q_{z}i=q_{z}j$ ${\ displaystyle q_ {z} i = q_ {z} j}$ ${\ displaystyle q_ {z} i = q_ {z} j}$ , adică cele două stări coincid în mulțimea Q și să fie v șirul lui z astfel încât ${\hat {\delta }}(q_{z}i,v)=q_{z}j$ ${\ displaystyle {\ hat {\ delta}} (q_ {z} i, v) = q_ {z} j}$ ${\ displaystyle {\ hat {\ delta}} (q_ {z} i, v) = q_ {z} j}$ .

Atâta timp cât $z\in L(A)$ ${\ displaystyle z \ în L (A)}$ ${\ displaystyle z \ în L (A)}$ Și $z=uvw$ ${\ displaystyle z = uvw}$ ${\ displaystyle z = uvw}$ , avem toate șirurile formei $uv^{k}w$ ${\ displaystyle uv ^ {k} w}$ ${\ displaystyle uv ^ {k} w}$ cu $k\geq 0$ ${\ displaystyle k \ geq 0}$ ${\ displaystyle k \ geq 0}$ ele vor fi recunoscute de automat, adică $uv^{k}w\in L(A)$ ${\ displaystyle uv ^ {k} w \ în L (A)}$ ${\ displaystyle uv ^ {k} w \ în L (A)}$ .

Bibliografie

( EN ) Yehoshua Bar-Hillel , MA Perles, E. Shamir, Despre proprietățile formale ale gramaticilor structurii de expresie simple , în Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung , vol. 14, 1961, pp. 143-172.
( EN ) John E. Hopcroft , Rajeev Motwani; Jeffrey D. Ullman , Proprietățile limbilor obișnuite , în Introducere în teoria automatelor, limbaje și calcul , Addison Wesley, 15 iulie 2006, ISBN 978-0-321-46225-1 .
(EN) Martin Davis , Ron Sigal; Elaine J. Weyuker, The Pumping Lemma and its Applications , in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science , Morgan Kaufmann, 17 februarie 1994, ISBN 978-0-12-206382-4 .

Elemente conexe

Lemă de pompare pentru limbi fără context

Portal IT

Portalul de matematică