به شما پیشنهاد می کنم کتاب نظریه زبانها و اتومات های پیتر لینز بخش ویزگی زبان های منظم رو بخونید. کامل همین مثال رو توضیح داده. و یک قسمت هم لم تزریق رو دقیقا مثل یک بازی فرض کرده.
من لم تزریق رو با استفاده از کتاب لینز براتون می گم:
لم تزریق:
فرض کنید L یک زبان منظم نامتناهی باشد.آنگاه عدد صحیح و مثبت m وجود دارد بطوریکه هر [tex]w\in L[/tex] را با شرط [tex]\left | w \right |\geqslant m[/tex]، می توان به صورت
[tex]w = xyz[/tex]
تجزیه کرد با فرض [tex]\left | xy \right |\leqslant m[/tex] و [tex]\left | y \right |\geqslant 1[/tex] بطوریکه [tex]w_{i} = xy^{i}z[/tex] به ازای تمام [tex]i = 0,1,2,3,...[/tex] عضو L خواهد بود.
برای این مثالی که شما گفتی ما اینجا مقدار عددی m رو نمی دونیم ولی می تونیم m=n انتخاب کنیم بنابراین زیر رشته y همشون a می شن اگر طول y رو k در نظر بگیریم اونوقت رشته بدست اومده در لم تزریق وقتی i=0 باشه، میشه: [tex]w_{0}=a^{m-k}b^{m}[/tex] که قطعا جزو زبان مون نیست چون تعدادش a,b برابر نیست.
فکر کنم تو اینجا مشکل داری: اگر لم تزریق حتی برای یک w هم نقض بشه دیگه اون زبان منظم نیست. به عبارت دیگه اگر زبانی منظم باشه در لم تزریق صدق می کنه. این لم بیشتر برای اثبات نا منظم بودن زبان هست و البته خیلی هم راحت نیست، اگر کسی بیاد ادعا کنه که این زبان منظمه و ما نتونیم با استفاده از لم تزریق ادعاشو رد کنیم پس زبان مورد نظر حتما منظمه. دم دست ترین اثبات نامنظم بودن یک زبان همین لم تزریق هست و اگر جواب نداد از راههای DFA و گرامر باید اثبات نامنظم بودن اونو کرد.
در هون کتابی که گفتم شبیه سازی بازیشو اینطوری نوشته:
استدلال صحیح برای یک زبان منظم را می توان نوعی بازی در برابر حریف تصور کرد.
هدف ما یعنی برنده شدن در بازی، به کمک ایجاد یک تناقض در لم تزریق بدست می آید. حریف هم تلاش می کند تا با ایده ای برنامه ریزی ما را بر هم بزند. در این بازی 4 حرکت انجام می شود:
1-حریف m را انتخاب می کند.
2- با در اختیار داشتم m ف رشته w از L را با طول بزرگتر مساوی m انتخاب می کنیم.ما در این انتخاب با این شرایطی که بیان شد ازادامی هر w را انتخاب کنیم.
3- حریف تجزیه xyz را با شرایط [tex]\left | xy \right |\leqslant m[/tex] و [tex]\left | y \right |\geqslant 1[/tex] انتخاب می کند. همواره باید به خاطر داشته باشیم حریف با انتخاب خود سعی می کند مانع از برنده شدن ما در بازی شود.
4- باید i را به گونه ای انتخاب کنیم که رشته پمپاژ شده [tex]w_{i}[/tex] عضو l نباشد. موفقیت در انتخاب i کلید برنده شدن ما در بازی است.
تو اون مثال ما با انتخاب n=m مجبور کردیم حریف رو که زیر رشتهy رو فقط از aها انتخاب کنه. ما با انتخاب درستمون که تو شرط [tex]\left | w \right | \geqslant m[/tex] صادق هست اینکارو کردیم. و درست آخر در i=0 حریف شکست خورد...
(18 خرداد 1390 06:42 ب.ظ)masoudkhan نوشته شده توسط: [ -> ]دوستان من لم تزریق رو چه برای اثبات نامنظم بودن یک زبان و هم چنین برای مستقل از متن بودن یک زبان خوندم اما مثالاش کمه و گاهی هم پیچیده
ممنون میشم یکی از دوستان با چند تا مثال و یه تعریف کاربردی منو از این گیجی دربیاره
[tex]L=\left \{ a^ib^i: i>0 \right \}[/tex]
می دونم مثلا اینجا کل AB میشه Z که حالا همین z به سه قسمت uvy تقسیم میشه که من باید یک رشته رو انتخاب کنم که اون رشته انتخابی من بر اساس اندیس i تزریقش کنم به رشته تا اثبات کنم که زبان در فرم قبلیش می مونه
اگر من v=a انتخاب کنم در اندیس i=1 بنابراین من a رو به رشته تزریق می کنم اما چون تعداد a بیشتر از b میشه پس زبان من منظم نیست و بهم می خوره درسته؟
اگر هم من b رو انتخاب کنم بازم بهم میریزه
حالا اگر من ab رو انتخاب کنم چطور ؟ اگر بتونم مشکلی دیگه نیست و تعداد به اندازه i تزریق میشه اما رشته بازم مرتبه درسته
اما به احتمال زیاد نمیشه حالا سوالم اینه که چرا نمیشه
اگر مربوط میشه به m لطفا بیشتر راهنماییم کنید که این m منو گیج کرده
ممنون
فردا صبح امتحان دارم این موضوع رو تا به الان حالیم نشده
حل التمرنی هم که دارم اصلا از روی لم تزریق پریده حلش نکرده
کاری که می کنیم در واقع همینه. شما باانتخاب اون a یا b کارو تموم کردی. نقض منظم بودن زبان با اون انتخاب تمومه دیگه. بله شما می تونی ab رو هم انتخاب کنی. کمکی بهت نمیکنه با استفاده از توضیحاتی که در همین بالا دادم. باید جوری انتخاب کنی که وقتی رشته رو تزریق می کنی اون رشته دیگه در زبان مورد نظر نباشه. انتخاب درست تو نقض می کنه منظم بودن رو که شما انجام دادی.یک مثال نقض پیدا شد و ادعای منظم بودن زبان رد...
اون m هم باید جوری انتخاب کنی که چاره ای نباشه برای حریف که رشتهy رو فقط از aها انتخاب کنه...