موضوع مقاله: لم تزریق برای زبان‌های منظم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # لم تزریق برای زبان‌های منظم | مقدمه: در نظریهٔ زبان‌های صوری، لم تزریق برای زبان‌های منظم یک ویژگی ضروری برای همهٔ زبان‌های منظم را توصیف می‌کند. | ## بخش 1: لم تزریق برای زبان‌های منظم | به‌طور غیر صوری، بیان می‌کند که هر کلمهٔ به اندازهٔ کافی بزرگ در یک زبان منظم می‌تواند تزریق شود — یعنی یک قسمت میانی کلمه به تعداد دل‌خواه تکرار شود — تا کلمهٔ جدیدی ایجاد شود که همچنین در همان زبان قرار گیرد. مخصوصا لم تزریق بیان می‌کند که برای هر زبان منظم L یک عدد ثابت p وجود دارد به‌طوری‌که هر کلمه w در L با طول حداقل p می‌تواند به سه زیر رشته تقسیم شود، w = xyz، که در آن بخش میانی y خالی نیست، طوری‌که کلمه‌های ساخته شده با به تعداد دل‌خواه بار تکرار y (شامل صفر بار) باز هم در L باشند. علاوه بر این، لم تزریق تضمین می‌کند که طول xy حداکثر p خواهد بود، که این محدودیتی بر راه‌هایی که w می‌تواند تقسیم شود تحمیل می‌کند. زبان‌های متناهی به وضوح لم تزریق را با قرار دادن p برابر طول بیشترین رشته در L به اضافهٔ یک ارضا می‌کنند. در این صورت عدد صحیح تنها وابسته به L وجود دارد طوری‌که هر رشتهٔ w در L با طول حداقل p (به p طول تزریق گفته می‌شود) می‌تواند به صورت w = xyz نوشته شود (w می‌تواند به سه زیررشته تقسیم شود)، طوری‌که شرط‌های زیر را ارضا کند: |y| ≥ 1; |xy| ≤ p for all i ≥ 0, xyiz ∈ L y زیر رشته‌ای است که می‌تواند تزریق شود (حذف شود یا به به هر تعداد بار تکرار شود، و رشتهٔ حاصل در هر حال در L باشد). |x| باید کوچکتر از p باشد (نتیجهٔ (۱) و (۲ ، غیر از این دیگر هیچ محدودیتی بر روی x و z وجود ندارد. به زبان ساده، برای هر زبان منظم L، هر کلمهٔ به اندازهٔ کافی بزرگ (در L) می‌تواند به ۳ قسمت تقسیم شود. در زیر یک صورت‌بندی صوری لم تزریق آمده‌است: کاربرد لم لم تزریق معمولاً برای اثبات نامنظم بودن یک زبان خاص مورد استفاده قرار می‌گیرد. یک اثبات به وسیلهٔ برهان خلف می‌تواند شامل یک کلمه (با طول خواسته شده) در زبان باشد که فاقد خاصیت بیان شده در لم تزریق است. به‌طور مثال زبان {L = {anbn : ≥ 0 روی الفبای {Σ = {a, b می‌تواند به روشی که در ادامه می‌آید اثبات شود که نامنظم است. | ## بخش 2: لم تزریق برای زبان‌های منظم | فرض کنید w، x، y، z، p و i همان متغیرهایی باشند که در صورت لم تزریق در بالا استفاده شدند. حال y را تزریق می‌کنیم: xy2z دارای نمونه‌های بیشتری از حرف a نسبت به حرف b است، زیرا ما تعدادی نمونهٔ a بدون اضافه کردن نمونه‌ای از b اضافه کردیم. اثبات لم تزریق برای هر زبان منظم یک ماشین حالات متناهی (FSA) وجود دارد که آن زبان را می‌پذیرد. تعداد حالات در چنین ماشین حالات متناهی‌ای شمرده می‌شود و این تعداد به عنوان طول تزریق p استفاده می‌شود. برای یک رشته به طول حداقل p، فرض کنید s0 حالت آغازین و s1, ..., sp ترتیب p حالت بعدی باشد که در فرایند تولید رشته طی می‌شوند. از آن‌جا که FSA تنها p حالت دارد، در این دنباله که در آن p+1 حالت طی شده‌است باید حداقل یک حالت وجود داشته باشد که تکرار شده‌است. انتقالاتی که ماشین را از اولین مواجهه با S به دومین مواجهه با S می‌برند با یک رشته تطابق دارند. این رشته در لم y نامیده می‌شود، و از آن‌جایی که ماشین بدون بخش y به یک رشته می‌رسد، یا رشتهٔ y می‌تواند به تعداد دل‌خواه بار تکرار شود، شرط‌های لم ارضا می‌شوند. از آن‌جا که این رشته طولی دارد که حداقل به اندازهٔ تعداد حالات است، اصل لانه کبوتری نشان می‌دهد که باید حداقل یک حالت تکراری بین حالت آغازین و ۴ حالت بعدی وجود داشته باشد. از آن‌جا که زیر رشتهٔ bc ماشین را درون انتقالاتی که در حالت q1 شروع می‌شوند و در حالت q1 تمام می‌شوند می‌برد، این قسمت می‌تواند با دادن رشتهٔ abcbcd تکرار شود و FSA هنوز می‌پذیرد. | ## بخش 3: لم تزریق برای زبان‌های منظم | این نسخه از لم می‌تواند در اثبات نامنظم بودن زبان‌های بیشتری مورد استفاده قرار بگیرد، زیرا شرایط سختگیرانه‌تری را روی زبان تحمیل می‌کند. عکس لم صحیح نیست در نظر داشته باشید با این که لم تزریق بیان می‌کند که هر زبان منظم شرایط بالا را ارضا می‌کنند، عکس این گزاره صحیح نیست: یک زبان که این شرایط را ارضا می‌کند ممکن است نامنظم باشد. به بیان دیگر، هر دو نسخهٔ اصلی و کلی لم تزریق یک شرط لازم و نه کافی را برای منظم بودن زبان ارائه می‌کنند. به بیان دیگر، L شامل همهٔ رشته‌ها روی الفبای {0,1،2,3} با یک زیر رشتهٔ به طول 3 شامل یک حرف تکراری است، و همچنین رشته‌هایی که دقیقاً 1/7 کاراکترهای آن رشته 3 باشند. سپس از آن‌جا که الفبا فقط 4 حرف دارد، حداقل دو تا از پنج حرف رشته باید تکراری باشند. اگر حرف‌های تکراری با 0 یا 1 حرف جدا شده باشند، یکی از دو حرف دیگر را که تأثیری روی زیررشته‌ای که شامل حروف تکراری است نداشته باشد تزریق می‌کنیم. اگر حروف تکراری با 2 یا 3 حرف جدا شده باشند، دو تا از حروفی که آن‌ها را از هم جدا می‌کند تزریق می‌کنیم. تزریق کردن بالا یا پایین یک زیررشته به طول 3 می‌سازد که که شامل دو حرف تکراری است. دومین شرط L تضمین می‌کند که L منظم نیست: به عنوان مثال، بی‌نهایت رشته در L وجود دارند که نمی‌توان با تزریق کردن یک رشتهٔ کوچک‌تر آن‌ها را به دست آورد. برای یک آزمایش عملی که دقیقاً زبان‌های منظم را مشخص می‌کند، نظریهٔ مایهیل-نروده را مشاهده کند. | ## جمع‌بندی | روش بارز برای اثبات منظم بودن یک زبان ساختن یک ماشین حالات متناهییا یک عبارت منظمبرای آن زبان است.