لم پمپاژ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

جستارهای وابسته[ویرایش]

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

زبان منظم

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

منابع[ویرایش]

  • 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