(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: این i چطور انتخاب میشه؟
i یک توانه. باید برای تمام حالات ممکن x و y و z بشه حداقل یک i پیدا کرد که رشته xy^{i}z جزء زبان نباشه. یعنی همیشه مثال نقض برای اثبات اینکه "هیچ حلقه ای وجود نداره" داشته باشیم. حریف ما تمام حالات شکستن رشته رو میگه. ما باید برای هرکدوم از این حالات یک توان بگیم که رشتش جزء زبان نباشه.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: مثلا برای زبان{۱ +a^ {m} b^ {m، نوشته بود |xy| نمیتونه بزرگتر از m باشه .خوب این درست.
و حریف کاری جز انتخاب y حاوی فقط a نمیتونه انجام بده!!!!! یعنی چی؟؟
M حرف اول رشتمون فقط a هست. چون فرضمون اینه که y در M حرف اول رشتست پس فقط میتونه یه تعدادی a باشه.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: حال با استفاده از i=2 رشته بدست آمده {w2= a^ {m+k} b^{m+1 میشود که در L نیست.
چرا مثلا واس i حدس زد که ۲ انتخاب بشه؟ چطوری!؟بهد که ۲ شد چرا {a^ {m+k شده
رشته اولمون xyz هست. وقتی i=2 بشه رشته جدیدمون میشه xyyz. درواقع i توان y هست. اگه برابر صفر بود رشته جدید میشد xz.
توی این مثال هر مقدار غیر از ۱ (بدیهیه که ۱ نمیتونه باشه) انتخاب کنیم جواب میده.
چرا M+k شد هم چون طول y یکبار دیگه تکرار شد. ابتدای رشته xyz تعداد Mتا a داریم. y هم kتا a داره و جزء Mتای اوله. پس اول رشته xyyz میشه M+kتا a.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: ی سوال دیگه واس {a^{M}b^{M چرا y فقط شامل a میتونه باشه؟ اگه w=ab در نظر بگیریم اونوقتم y فقط شمال ( ) b هست یا واس M بزرگ شامل a هست ک گفتین ؟
مقدار M بزرگ فرض شده. بزرگتر از تعداد حالات ماشینمون. شما M رو ۱ فرض کردید. فرض قضیه رو نقض کردید.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: مثلا aaabbb اونوقت میشه این xy رو همه aaabbb در نظر گرفت؟؟؟ x رو چی انتخاب کنیم؟ y رو چی؟
aaabb میشه x و
b مثلا y !!!
اینام میشه پس؟
رشتمون {a^{M}b^{M هست. تعداد حالت ماشینمون باید حداکثر M-1 باشه. درضمن xy کوچکتر مساویه M هست. اصلاً دنبال مثال به این شکل نباشید.