لم تزریق

در علوم رایانه در بحث نظریه زبان‌ها، لم تزریق یا پامپینگ لما (به انگلیسی: Pumping lemma) بیان می‌کند که: برای یک زبان خاص به عنوان یک عضو از یک نوع زبان، هر رشته به اندازه کافی طولانی در این زبان، شامل یک بخش، یا بخش‌هایی است، که می‌تواند حذف شود، یا هر تعداد باری تکرار شود که رشته‌های نتیجه شده در آن زبان می‌باشد.

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

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

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

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

زبان منظم

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

منابع

• 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