لم پمپاژ برای زبان‌های منظم

در نظریهٔ زبان‌های صوری، لم پمپاژ برای زبان‌های منظم یک ویژگی ضروری برای همهٔ زبان‌های منظم را توصیف می‌کند. به‌طور غیر صوری، بیان می‌کند که هر کلمهٔ به اندازهٔ کافی بزرگ در یک زبان منظم می‌تواند پمپاژ شود — یعنی یک قسمت میانی کلمه به تعداد دل‌خواه تکرار شود — تا کلمهٔ جدیدی ایجاد شود که همچنین در همان زبان قرار گیرد.
مخصوصا لم پمپاژ بیان می‌کند که برای هر زبان منظم L یک عدد ثابت p وجود دارد به‌طوری‌که هر کلمه w در L با طول حداقل p می‌تواند به سه زیر رشته تقسیم شود، w = xyz، که در آن بخش میانی y خالی نیست، طوری‌که کلمه‌های xz، xyz، xyyz، xyyyz، ... ساخته شده با به تعداد دل‌خواه بار تکرار y (شامل صفر بار) باز هم در L باشند. این فرایند تکرار به «پمپاژ» معروف است. علاوه بر این، لم پمپاژ تضمین می‌کند که طول xy حداکثر p خواهد بود، که این محدودیتی بر راه‌هایی که w می‌تواند تقسیم شود تحمیل می‌کند. زبان‌های متناهی به وضوح لم پمپاژ را با قرار دادن p برابر طول بیشترین رشته در L به اضافهٔ یک ارضا می‌کنند.
لم پمپاژ اولین بار توسط دانا اسکات و مایکل رابین در ۱۹۵۹ اثبات شد.
این لم برای رد کردن خاصیت منظم بودن یک زبان خاص مورد سؤال کاربرد دارد. این لم یکی از معدود لم‌های پمپاژ است، که هر کدام قصد مشابهی دارند.

کاربرد لم

لم پمپاژ معمولاً برای اثبات نامنظم بودن یک زبان خاص مورد استفاده قرار می‌گیرد. یک اثبات به وسیلهٔ برهان خلف می‌تواند شامل یک کلمه (با طول خواسته شده) در زبان باشد که فاقد خاصیت بیان شده در لم پمپاژ است.
به‌طور مثال زبان {L = {aⁿbⁿ : ≥ 0 روی الفبای {Σ = {a, b می‌تواند به روشی که در ادامه می‌آید اثبات شود که نامنظم است. فرض کنید w، x، y، z، p و i همان متغیرهایی باشند که در صورت لم پمپاژ در بالا استفاده شدند. فرض کنید w در L به صورت w = aᵖbᵖ داده شده باشد. با استفاده از لم پمپاژ، باید یک تجزیه w = xyz با xy| ≤ p| و y| ≥ 1| وجود داشته باشد طوری‌که xyⁱz به ازای هر i در L باشد. با استفاده از xy| ≤ p| می‌دانیم که y فقط شامل نمونه‌های a است. علاوه بر این، چون y| ≥ 1|، شامل حداقل یک نمونه از a است. حال y را پمپاژ می‌کنیم: xy²z دارای نمونه‌های بیشتری از حرف a نسبت به حرف b است، زیرا ما تعدادی نمونهٔ a بدون اضافه کردن نمونه‌ای از b اضافه کردیم. بنابراین xy²z در L نیست. پس به تناقض رسیدیم. از این رو، این فرض که L منظم است باید نادرست باشد. پس L منظم نیست.

اثبات لم پمپاژ

برای هر زبان منظم یک ماشین حالات متناهی (FSA) وجود دارد که آن زبان را می‌پذیرد. تعداد حالات در چنین ماشین حالات متناهی‌ای شمرده می‌شود و این تعداد به عنوان طول پمپاژ p استفاده می‌شود. برای یک رشته به طول حداقل p، فرض کنید s₀ حالت آغازین و s₁, ..., sₚ ترتیب p حالت بعدی باشد که در فرایند تولید رشته طی می‌شوند. از آن‌جا که FSA تنها p حالت دارد، در این دنباله که در آن p+1 حالت طی شده‌است باید حداقل یک حالت وجود داشته باشد که تکرار شده‌است. نام این حالت را S می‌گذاریم. انتقالاتی که ماشین را از اولین مواجهه با S به دومین مواجهه با S می‌برند با یک رشته تطابق دارند. این رشته در لم y نامیده می‌شود، و از آن‌جایی که ماشین بدون بخش y به یک رشته می‌رسد، یا رشتهٔ y می‌تواند به تعداد دل‌خواه بار تکرار شود، شرط‌های لم ارضا می‌شوند.
به‌طور مثال شکل زیر یک FSA را نشان می‌دهد:
FSA رشتهٔ abcd را می‌پذیرد. از آن‌جا که این رشته طولی دارد که حداقل به اندازهٔ تعداد حالات است، اصل لانه کبوتری نشان می‌دهد که باید حداقل یک حالت تکراری بین حالت آغازین و ۴ حالت بعدی وجود داشته باشد. در این مثال فقط q₁ حالت تکراری است. از آن‌جا که زیر رشتهٔ bc ماشین را درون انتقالاتی که در حالت q₁ شروع می‌شوند و در حالت q₁ تمام می‌شوند می‌برد، این قسمت می‌تواند با دادن رشتهٔ abcbcd تکرار شود و FSA هنوز می‌پذیرد. متناوباً، قسمت bc می‌تواند حذف شود و FSA کماکان دادن رشتهٔ ad را می‌پذیرد. در عبارات لم پمپاژ، رشتهٔ abcd شکسته شده به یک قسمت x که a است، یک قسمت y که bc است و یک قسمت z که d است.