در نظریهٔ زبان های صوری، لم پمپاژ برای زبان های منظم یک ویژگی ضروری برای همهٔ زبان های منظم را توصیف می کند. به طور غیر صوری، بیان می کند که هر کلمهٔ به اندازهٔ کافی بزرگ در یک زبان منظم می تواند پمپاژ شود — یعنی یک قسمت میانی کلمه به تعداد دل خواه تکرار شود — تا کلمهٔ جدیدی ایجاد شود که همچنین در همان زبان قرار گیرد.
مخصوصا لم پمپاژ بیان می کند که برای هر زبان منظم L یک عدد ثابت p وجود دارد به طوری که هر کلمه w در L با طول حداقل p می تواند به سه زیر رشته تقسیم شود، w = xyz، که در آن بخش میانی y خالی نیست، طوری که کلمه های xz، xyz، xyyz، xyyyz، . . . ساخته شده با به تعداد دل خواه بار تکرار y ( شامل صفر بار ) باز هم در L باشند. این فرایند تکرار به «پمپاژ» معروف است. علاوه بر این، لم پمپاژ تضمین می کند که طول xy حداکثر p خواهد بود، که این محدودیتی بر راه هایی که w می تواند تقسیم شود تحمیل می کند. زبان های متناهی به وضوح لم پمپاژ را با قرار دادن p برابر طول بیشترین رشته در L به اضافهٔ یک ارضا می کنند.
لم پمپاژ اولین بار توسط دانا اسکات و مایکل رابین در ۱۹۵۹ اثبات شد. [ ۱] این لم برای رد کردن خاصیت منظم بودن یک زبان خاص مورد سؤال کاربرد دارد. این لم یکی از معدود لم های پمپاژ است، که هر کدام قصد مشابهی دارند.
فرض می کنیم L یک زبان منظم باشد. در این صورت عدد صحیح p ≥ 1 تنها وابسته به L وجود دارد طوری که هر رشتهٔ w در L با طول حداقل p ( به p طول پمپاژ گفته می شود ) می تواند به صورت w = xyz نوشته شود ( w می تواند به سه زیررشته تقسیم شود ) ، طوری که شرط های زیر را ارضا کند:
• |y| ≥ 1;
• |xy| ≤ p
• for all i ≥ 0, xyiz ∈ L
y زیر رشته ای است که می تواند پمپاژ شود ( حذف شود یا به به هر تعداد بار تکرار شود، و رشتهٔ حاصل در هر حال در L باشد ) . ( ۱ ) به این معنی است که طول لوپ y که پمپاژ می شود باید حداقل یک باشد. ( ۲ ) به این معنی است که لوپ y باید در p کاراکتر اول واقع باشد. |x| باید کوچکتر از p باشد ( نتیجهٔ ( ۱ ) و ( ۲ ) ) ، غیر از این دیگر هیچ محدودیتی بر روی x و z وجود ندارد.
به زبان ساده، برای هر زبان منظم L، هر کلمهٔ به اندازهٔ کافی بزرگ ( در L ) می تواند به ۳ قسمت تقسیم شود. مثلاً w = xyz، طوری که همهٔ رشته های xykz برای هر k≥0 هم در L باشند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمخصوصا لم پمپاژ بیان می کند که برای هر زبان منظم L یک عدد ثابت p وجود دارد به طوری که هر کلمه w در L با طول حداقل p می تواند به سه زیر رشته تقسیم شود، w = xyz، که در آن بخش میانی y خالی نیست، طوری که کلمه های xz، xyz، xyyz، xyyyz، . . . ساخته شده با به تعداد دل خواه بار تکرار y ( شامل صفر بار ) باز هم در L باشند. این فرایند تکرار به «پمپاژ» معروف است. علاوه بر این، لم پمپاژ تضمین می کند که طول xy حداکثر p خواهد بود، که این محدودیتی بر راه هایی که w می تواند تقسیم شود تحمیل می کند. زبان های متناهی به وضوح لم پمپاژ را با قرار دادن p برابر طول بیشترین رشته در L به اضافهٔ یک ارضا می کنند.
لم پمپاژ اولین بار توسط دانا اسکات و مایکل رابین در ۱۹۵۹ اثبات شد. [ ۱] این لم برای رد کردن خاصیت منظم بودن یک زبان خاص مورد سؤال کاربرد دارد. این لم یکی از معدود لم های پمپاژ است، که هر کدام قصد مشابهی دارند.
فرض می کنیم L یک زبان منظم باشد. در این صورت عدد صحیح p ≥ 1 تنها وابسته به L وجود دارد طوری که هر رشتهٔ w در L با طول حداقل p ( به p طول پمپاژ گفته می شود ) می تواند به صورت w = xyz نوشته شود ( w می تواند به سه زیررشته تقسیم شود ) ، طوری که شرط های زیر را ارضا کند:
• |y| ≥ 1;
• |xy| ≤ p
• for all i ≥ 0, xyiz ∈ L
y زیر رشته ای است که می تواند پمپاژ شود ( حذف شود یا به به هر تعداد بار تکرار شود، و رشتهٔ حاصل در هر حال در L باشد ) . ( ۱ ) به این معنی است که طول لوپ y که پمپاژ می شود باید حداقل یک باشد. ( ۲ ) به این معنی است که لوپ y باید در p کاراکتر اول واقع باشد. |x| باید کوچکتر از p باشد ( نتیجهٔ ( ۱ ) و ( ۲ ) ) ، غیر از این دیگر هیچ محدودیتی بر روی x و z وجود ندارد.
به زبان ساده، برای هر زبان منظم L، هر کلمهٔ به اندازهٔ کافی بزرگ ( در L ) می تواند به ۳ قسمت تقسیم شود. مثلاً w = xyz، طوری که همهٔ رشته های xykz برای هر k≥0 هم در L باشند.
