لم پمپاژ

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

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

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

جستارهای وابسته 
نظریه رایانش‌پذیری

زبان منظم

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

منابع 

  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.
  Chapter 6: Properties of Regular Languages pp. 205–210

دستور زبان
روش‌های صوری
زبان‌های صوری
زبان‌های فراساخته
علوم صوری
علوم نظری رایانه
فرامنطق
لم‌ها
مجموعه‌نمایه‌ها