مثال ۱۳ فصل چهار کتاب لینز خواسته نشون بدیم زبان زیر منظم نیست:
کد:
L = { a^n b^L: n != L}من برای حل این سؤال w رو a^m b^m+m! l گرفتم، و به نظرم خیلی ساده‌تر و قابل فهم‌تر اومد! بعد شک کردم که شاید دارم اشتباه میکنم یه جایی! خواستم بپرسم این w هم درسته؟
(من i رو میگیرم ۱ + m! / K)
(۲۹ شهریور ۱۳۸۹ ۰۲:۵۴ ب.ظ)۵۴m4n3h نوشته شده توسط: مثال ۱۳ فصل چهار کتاب لینز خواسته نشون بدیم زبان زیر منظم نیست:من این مباحث رو مسلط نیستم ولی فکر میکنم این انتخابتون اشکال داره.
wی لم پامپینگ رو a^m! b^(m+1)! l گرفته.کد:
L = { a^n b^L: n != L}
من برای حل این سؤال w رو a^m b^m+m! l گرفتم، و به نظرم خیلی ساده‌تر و قابل فهم‌تر اومد! بعد شک کردم که شاید دارم اشتباه میکنم یه جایی! خواستم بپرسم این w هم درسته؟
(من i رو میگیرم ۱ + m! / K)
توی حالتی که شما گرفتید اگر حریف بیاد یک y از b انتخاب کنه.خواهیم داشت:
XXX W=a^m b^m-k b^k b^m! XXX
XXX W=a^m b^m+m!+k(i-1) XXX
حالا شما باید به عنوان رقیب ثابت کنید که
XXX m = m+m!+k(i-1) XXX
که امکان پذیر نیست.اشتباه که نگفتم؟
طول xy باید کوچکتر از m باشه، یعنی حریف مجبوره y رو از توی aها انتخاب کنه.
(۲۹ شهریور ۱۳۸۹ ۰۹:۲۹ ب.ظ)۵۴m4n3h نوشته شده توسط: طول xy باید کوچکتر از m باشه، یعنی حریف مجبوره y رو از توی aها انتخاب کنه.m که دست خودتونه(سور وجودیه).می تونید بگید:
طول W بزرگتر مساوی XXX 2m+m! XXX هست.در نتیجه طول xy همیشه از اون کوچکتره.
دلیل اصلی اینکه توی قضیه هم بزرگتر مساوی گذاشته همین بوده که سعی کنید ماکزیممشو بگیرید.
اگر اشتباه میکنم ممنون میشم که بگید.
(۲۹ شهریور ۱۳۸۹ ۱۱:۳۱ ب.ظ)حامد نوشته شده توسط:فرض میکنیم که حریف m رو انتخاب کرده و ما باید یه w انتخاب کنیم که طولش حداقل m باشه مثلاً این جا ۲m+m! l هست بعد حریف xy رو طوری انتخاب میکنه که حداکثر طولش m باشه؛ یعنی طول xy همیشه باید کوچکتر از m باشه.(29 شهریور ۱۳۸۹ ۰۹:۲۹ ب.ظ)۵۴m4n3h نوشته شده توسط: طول xy باید کوچکتر از m باشه، یعنی حریف مجبوره y رو از توی aها انتخاب کنه.m که دست خودتونه(سور وجودیه).می تونید بگید:
طول W بزرگتر مساوی XXX 2m+m! XXX هست.در نتیجه طول xy همیشه از اون کوچکتره.
دلیل اصلی اینکه توی قضیه هم بزرگتر مساوی گذاشته همین بوده که سعی کنید ماکزیممشو بگیرید.
اگر اشتباه میکنم ممنون میشم که بگید.
فکر کنم اگه این طوری که شما میگید باشه، هیچ وقت نشه از لم پامپینگ برای اثبات نامنظم بودن هر زبان نامنظمی استفاده کرد.
بله.انگاری حق باشماست.چونکه مثالی پیدا نکردم که به روشی که خودم میگفتم در نظر بگیره.
اگر اینطوری باشه که روش شما هم مشکلی نمی تونه داشته باشه.
چرا بقیه اینجا جواب سوالات رو نمی دند؟
