لم تزریق بدون ترس: اثبات نامنظم بودن به‌شکل یک بازی دونفره

قانون بازی

تو p را نمی‌دانی و شکستن را هم نمی‌دانی؛ پس s و i را باید طوری بچینی که برای هر p و هر شکستن ممکن کار کنند. کلید تقریباً همهٔ بازی‌ها شرط |xy| ≤ p است: y همیشه جایی در p نماد اول s است. اگر s را طوری انتخاب کنی که p نماد اولش همه یک‌جور باشند، می‌دانی y دقیقاً از چه ساخته شده است.

بازی ۱: 0ⁿ1ⁿ

حریف p را می‌دهد. تو s = 0ᵖ1ᵖ را انتخاب کن. چون |xy| ≤ p، هر شکستنی که حریف بکند، y فقط از ۰ ساخته شده و دست‌کم یک ۰ دارد. حالا i = 2 را انتخاب کن: رشتهٔ xy²z تعداد ۰ بیشتری از ۱ دارد و در L نیست. i = 0 هم کار می‌کند، چون تعداد ۰ کمتر می‌شود. برنده شدی؛ زبان نامنظم است.

بازی ۲: ww، رشته‌هایی که از تکرار یک رشته ساخته شده‌اند

اینجا انتخاب s مهم است. اگر s = 0²ᵖ را انتخاب کنی، بازی را می‌بازی: این رشته در L هست، ولی حریف y = 00 را از ابتدای رشته برمی‌دارد و هر تعداد تکرار از آن، رشتهٔ ۰های با طول زوج می‌سازد که باز هم در L است.

انتخاب درست s = 0ᵖ1 0ᵖ1 است. y باز هم فقط از ۰های نیمهٔ اول است. با i = 2 نیمهٔ اول بلندتر می‌شود و رشته دیگر به‌شکل ww نیست. درس این بازی: رشته‌ای انتخاب کن که ساختار زبان را «قفل» کند، نه رشته‌ای که به‌شکل تصادفی در زبان هست.

بازی ۳: 0 به توان مربع کامل

زبان رشته‌هایی از ۰ که طولشان مربع کامل است: ۰، ۱، ۴، ۹، ۱۶، …. s = 0^(p²) را انتخاب کن. y بین ۱ تا p صفر دارد. با i = 2 طول رشته بین p² + 1 و p² + p می‌شود. ولی مربع کامل بعدی (p + 1)² = p² + 2p + 1 است، که از p² + p بزرگ‌تر است. پس طول جدید بین دو مربع کامل پشت‌سرهم افتاده و مربع کامل نیست.

بازی ۴: 1 به توان عدد اول

زبان رشته‌هایی از ۱ که طولشان عدد اول است. یک عدد اول q ≥ p + 2 بردار و s = 1^q را انتخاب کن. فرض کن y طول k دارد. i را برابر q + 1 بگیر. طول رشتهٔ جدید q + qk = q(1 + k) می‌شود که حاصل‌ضرب دو عدد بزرگ‌تر از ۱ است، پس اول نیست.

بازی ۵: وقتی باید پایین تزریق کنی

زبان 0ⁱ1ʲ با i > j، یعنی رشته‌هایی که اول ۰ و بعد ۱ دارند و تعداد ۰ها بیشتر است. s = 0^(p+1)1ᵖ را انتخاب کن. اگر مثل بازی ۱ با i = 2 تکرار کنی، ۰ها بیشتر می‌شوند و رشته هنوز در L است؛ این انتخاب می‌بازد. انتخاب درست i = 0 است: y حذف می‌شود، دست‌کم یک ۰ کم می‌شود و تعداد ۰ها دیگر از ۱ها بیشتر نیست.

این بازی نشان می‌دهد i = 0، یعنی «پایین تزریق کردن»، هم یک حرکت مجاز و گاهی تنها حرکت برنده است.

سه اشتباهی که اثبات را بی‌اعتبار می‌کند

اشتباه ۱: انتخاب شکستن به‌جای حریف

رایج‌ترین اشتباه این است که بنویسی «فرض کن y = 01» و بعد نشان بدهی برای همین شکستن رشته از زبان بیرون می‌افتد. شکستن را حریف انتخاب می‌کند. تو باید نشان بدهی برای هر شکستنی با |xy| ≤ p و |y| ≥ 1 برنده‌ای. برای همین رشته‌ای انتخاب می‌کنی که p نماد اولش یک‌جور باشند تا حالت‌بندی لازم نباشد.

اشتباه ۲: انتخاب رشته‌ای که شرط‌ها را ندارد

s باید در L باشد و طولش دست‌کم p باشد، برای هر p. رشته‌ای مثل 0³1³ با طول ثابت کافی نیست، چون حریف می‌تواند p را بزرگ‌تر از ۶ انتخاب کند. رشته‌ات باید به p وابسته باشد.

اشتباه ۳: نتیجه گرفتن منظم بودن از برقرار بودن لم

لم تزریق فقط یک طرفه است: هر زبان منظم در آن صدق می‌کند، ولی هر زبانی که در آن صدق کند منظم نیست. مثال کلاسیک زبان aⁱbʲcᵏ است با این شرط که اگر i = 1 باشد آن‌وقت j = k. این زبان منظم نیست، ولی با p = 2 در لم تزریق صدق می‌کند؛ ما این را برای همهٔ رشته‌های این زبان تا طول ۹ با کد بررسی کردیم. پس اگر در بازی نتوانستی برنده شوی، این ثابت نمی‌کند زبان منظم است؛ فقط یعنی باید ابزار دیگری امتحان کنی.

پرسش‌های پرتکرار

i را همیشه ۲ بگیرم؟

نه. i = 2 رایج‌ترین انتخاب است، ولی در زبان‌هایی مثل 0ⁱ1ʲ با i > j باید i = 0 بگیری. در زبان‌هایی که با عدد اول یا مضرب کار دارند هم گاهی i بزرگ، مثل q + 1، لازم است.

اگر لم تزریق جواب نداد چه کنم؟

دو ابزار دیگر داری. خواص بستاری: اگر L منظم بود، اشتراکش با یک زبان منظم هم منظم می‌شد؛ مثلاً اشتراک «تعداد برابر ۰ و ۱» با 0*1* همان 0ⁿ1ⁿ است که نامنظم است. ابزار دوم مایهیل–نرود است: بی‌نهایت پیشوند پیدا کن که هر دوتایشان با یک پسوند از هم جدا شوند.

لم تزریق زبان‌های مستقل از متن چه فرقی دارد؟

ایده همان است ولی رشته به پنج تکه شکسته می‌شود، uvxyz، و دو تکهٔ v و y هم‌زمان تکرار می‌شوند. شرط |vxy| ≤ p جای شرط |xy| ≤ p را می‌گیرد؛ یعنی تکه‌های تکرارشونده می‌توانند هر جای رشته باشند، نه فقط در ابتدا. این باعث می‌شود حالت‌بندی بیشتری لازم شود.

چطور رشتهٔ مناسب را انتخاب کنم؟

رشته‌ای انتخاب کن که در L باشد، به p وابسته باشد، p نماد اولش یک‌جور باشند و روی مرز زبان باشد؛ یعنی کوچک‌ترین تغییر در یک بخشش آن را از زبان بیرون بیندازد. 0ᵖ1ᵖ برای تعداد برابر و 0^(p+1)1ᵖ برای «یکی بیشتر» نمونه‌های همین قاعده‌اند.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم و نظریهٔ زبان‌ها و ماشین‌ها را در کلاس نظریه درس می‌دهم؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. در ۱۴۰۵ آقای کاظمی و آقای احمدی، دو نفر از شاگردهای همین کلاس، هر پنج تست نظریه را درست زدند؛ پاسخ‌هایشان در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

این سه زبان را خودت بازی کن و فقط s و i را بنویس: ۱) رشته‌های 0ⁿ1²ⁿ ۲) رشته‌هایی از ۰ که طولشان توانی از ۲ است ۳) رشته‌های 0ⁱ1ʲ با i ≠ j.

راهنمایی‌ها: ۱) s = 0ᵖ1²ᵖ و i = 2. ۲) s = 0^(2ᵖ) و i = 2؛ طول جدید بین 2ᵖ و 2ᵖ⁺¹ می‌افتد. ۳) این یکی با لم تزریق مستقیم سخت است؛ از بستار استفاده کن: مکملش را با 0*1* قطع کن تا به 0ⁿ1ⁿ برسی.