لم پمپاژ

در تئوری‌های زبان صوری در نظریه رایانش‌پذیری، لم پمپاژ یا بحٍث پمپاژ بیان می‌کند که:برای یک زبان خاص به عنوان یک عضو از یک نوع زبان، هر رشته به اندازه کافی طولانی در این زبان، شامل یک بخش، یا بخش‌هایی است، که می‌تواند حذف شود، یا هر تعداد باری تکرار شود که رشته‌های نتیجه شده در آن زبان می‌باشد.

دو مثال مهم لم پمپاژ برای زبان منظم و لم پمپاژ برای متن مستقل از زبان است. لم اوگدن دومی و قویترین لم پمپاژ برای متن مستقل از زبان است.

از این لم‌ها برای تعیین اینکه که آیا زبان خاصی در کلاسی از زبان‌ها استفاده شده‌است یا نه، استفاده کرد. با این حال، از آن‌ها نمی‌توان برای تعیین اینکه آیا از زبان در کلاس هستند، استفاده کرد، چون وجود لم پمپاژ لازم است ولی برای عضویت در کلاس کافی نیست.

جستارهای وابسته

نظریه رایانش‌پذیری

زبان منظم

گرامر مستقل از متن

منابع

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.
• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5. Chapter 6: Properties of Regular Languages pp. 205–210