سلام دوستان من چندین بار کتاب و خوندم تا لم تزریق برای اثبات نا منظم بودن زبان و درک کنم . کلیات و مراحلش و فهمیدم اما در بکارگیری این تکنیک ها در حل مسئله دچار مشکل میشم . یک مثال ساده ضمیمه کردم لطفا سوالات مربوط رو با توجه ب مثال ها توضیح بدید
مرسی
۱/حریف عدد طبیعی n انتخاب می کند آیا هر عددی می تواند باشد و فقط باید عدد صحیح باشه ؟
۲/آیا همیشه می توان این نتیجه را گرفت چون [tex]|xy|\le n[/tex] و [tex]|y|\ge1[/tex] پس [tex]1\le|y|\le n[/tex] ?
۳/چرا تو مثال ضمیمه شده رشته شکسته شده به xyz ، مقدار z برابر با [tex]a^{n-(m k)}b^n[/tex] شده ؟
۴/ در نهایت مقدار تزریق i بر چه اساسی انتخاب می شود
با نهایت تشکر
![[تصویر: 389797_photo_2015_11_09_13_36_37.jpg]](https://img.manesht.ir/389797_photo_2015_11_09_13_36_37.jpg)
سلام. عکس برای من باز نشد. کلیات لم تزریق بصورت خلاصه:
یک زبان معرفی میشه.
میبایست یک رشته که طولش از یک عدد بزرگ M بیشتره رو پیدا کنیم که M رو اندازه ماشین درنظر میگیریم (برای اینکه درنظر بگیریم رشته توی یه حلقه افتاده.)
این رشته رو به تمام حالات ممکن میشکنیم و محلهای قرار گرفتن اون حلقه رو درنظر میگیریم.
ثابت میکنیم به ازای تمام حالات شکستن رشته میشه یه تعداد تکرار برای حلقه پیدا کرد که رشته جدید عضو زبان نباشه.
(۱۹ آبان ۱۳۹۴ ۰۲:۵۱ ق.ظ)Jooybari نوشته شده توسط: سلام. عکس برای من باز نشد. کلیات لم تزریق بصورت خلاصه:مرسی لطف می کنید همین مراحل رو برای زبان ساده ای مثل ، رشته w , که داریم wwreverse برای مجموعه تمام حالت های a , b مرحله مرحله حل کنید ، مخصوص طریقه تجزیه و شکستن رشته به xyz .
یک زبان معرفی میشه.
میبایست یک رشته که طولش از یک عدد بزرگ M بیشتره رو پیدا کنیم که M رو اندازه ماشین درنظر میگیریم (برای اینکه درنظر بگیریم رشته توی یه حلقه افتاده.)
این رشته رو به تمام حالات ممکن میشکنیم و محلهای قرار گرفتن اون حلقه رو درنظر میگیریم.
ثابت میکنیم به ازای تمام حالات شکستن رشته میشه یه تعداد تکرار برای حلقه پیدا کرد که رشته جدید عضو زبان نباشه.
با تشکر
Sent from my SM-P601 using Tapatalk
(۱۹ آبان ۱۳۹۴ ۱۰:۲۴ ق.ظ)joyebright نوشته شده توسط: همین مراحل رو برای زبان ساده ای مثل ، رشته w , که داریم wwreverse برای مجموعه تمام حالت های a , b مرحله مرحله حل کنید ، مخصوص طریقه تجزیه و شکستن رشته به xyz .
برای زبان [tex]L=\{ww^r|w\in {\sum}^*\}[/tex]. فرض کنید ماشین متناهی که قراره این زبان رو قبول کنه طول p داره. یک عدد q بزرگتر از p رو درنظر میگیریم. دلیل این فرض اینه که قصد داریم یه رشته با طول بزرگتر از اندازه حالت های ماشین که جزء زبانه رو مثال بزنیم.
رشته [tex]a^qbba^q[/tex] رشته ای از زبانه.
این رشته رو به تمام حالات ممکن میشکنیم به طوری که [tex]|xy|\leq p[/tex] و [tex]|y|\geq 1[/tex] باشه. منظور از این دو عبارت اینه که اگه قراره رشته انتخابی توی ماشین متناهی یه جایی توی حلقه بیافته، این حلقه حتما توی p حرف اول رشته اتفاق افتاده و اندازه این حلقه حداقل برابر ۱ و حداکثر به اندازه تعداد حالتهای ماشینه. چون ماشین قابلیت شمردن تعداد حلقه هارو نداره، میگیم اگه تعداد تکرارهای اون حلقه تغییر کنه یاز هم باید رشته تولید شده عضو زبان باشه. اگه برای یک رشته از زبان بتونیم برای تمام حالات شکستنش، یک توان پیدا کنیم که رشته جدید عضو زبان نباشه، زبان منظم نیست.
تمام حالتهای این انتخاب با انتخاب تعدادی از حروف a مجموعه اول همراهه. اگه توان رو برابر ۲ بگیریم چی میشه؟ یه تعداد به a های اول رشته اضافه میشه و رشته جدید عضو زبان نخواهد بود. پس زبان منظم نیست.
(۲۰ آبان ۱۳۹۴ ۰۲:۳۴ ق.ظ)Jooybari نوشته شده توسط:(19 آبان ۱۳۹۴ ۱۰:۲۴ ق.ظ)joyebright نوشته شده توسط: همین مراحل رو برای زبان ساده ای مثل ، رشته w , که داریم wwreverse برای مجموعه تمام حالت های a , b مرحله مرحله حل کنید ، مخصوص طریقه تجزیه و شکستن رشته به xyz .
برای زبان [tex]L=\{ww^r|w\in {\sum}^*\}[/tex]. فرض کنید ماشین متناهی که قراره این زبان رو قبول کنه طول p داره. یک عدد q بزرگتر از p رو درنظر میگیریم. دلیل این فرض اینه که قصد داریم یه رشته با طول بزرگتر از اندازه حالت های ماشین که جزء زبانه رو مثال بزنیم.
رشته [tex]a^qbba^q[/tex] رشته ای از زبانه.
این رشته رو به تمام حالات ممکن میشکنیم به طوری که [tex]|xy|\leq p[/tex] و [tex]|y|\geq 1[/tex] باشه. منظور از این دو عبارت اینه که اگه قراره رشته انتخابی توی ماشین متناهی یه جایی توی حلقه بیافته، این حلقه حتما توی p حرف اول رشته اتفاق افتاده و اندازه این حلقه حداقل برابر ۱ و حداکثر به اندازه تعداد حالتهای ماشینه. چون ماشین قابلیت شمردن تعداد حلقه هارو نداره، میگیم اگه تعداد تکرارهای اون حلقه تغییر کنه یاز هم باید رشته تولید شده عضو زبان باشه. اگه برای یک رشته از زبان بتونیم برای تمام حالات شکستنش، یک توان پیدا کنیم که رشته جدید عضو زبان نباشه، زبان منظم نیست.
تمام حالتهای این انتخاب با انتخاب تعدادی از حروف a مجموعه اول همراهه. اگه توان رو برابر ۲ بگیریم چی میشه؟ یه تعداد به a های اول رشته اضافه میشه و رشته جدید عضو زبان نخواهد بود. پس زبان منظم نیست.
۱/منظورتون از یک عدد q بزرگتر از p همون رشته w که طولش بیشتر از q باشه دیگه ؟
۲/می شد مثلا به جای رشته انتخابی شما abba انتخاب می کردیم و چرا a به توان q رسیده ؟
(۲۰ آبان ۱۳۹۴ ۱۲:۱۹ ب.ظ)joyebright نوشته شده توسط: ۱/منظورتون از یک عدد q بزرگتر از p همون رشته w که طولش بیشتر از q باشه دیگه ؟
بله میشه گفت. یه رشته با توجه به پارامتر q که میدونیم بزرگتر از p هست انتخاب میکنیم.
(۲۰ آبان ۱۳۹۴ ۱۲:۱۹ ب.ظ)joyebright نوشته شده توسط: ۲/می شد مثلا به جای رشته انتخابی شما abba انتخاب می کردیم و چرا a به توان q رسیده ؟
خیر نمیشه. این رشته ای که انتخاب کردم باعث میشه بدونیم برای اینکه این زبان منظم باشه باید یه حلقه توی p حرف اول این رشته اتفاق افتاده باشه. توان q هم برای اینه که مطمئن بشیم حلقه حتماً توی حروف a اول رشته اتفاق افتاده.