تناقض در لم پامپ
به نام خدا
سلام بر علما
من روی لم پمپ کار می کنم اما می بینم تناقضی هست. به عنوان مثال
{a^i .b^j. c^k: k>i , k>j}
در حل التمرینات لینز نوشته که ما W را a^m. b^m .c^m+1 می گیریم. خوب معلومه که این زبان مستقل از متن نیست. اما من یک حالت دیگه معرفی می کنم که مستقل از متن باشه مثلا
a^n.b^m.c^n+m
می بینیم که مستقل از متن شد.
حالا سوال:
۱ - آیا برای لم پامپ باید هر طور شده یک رشته مثل W تولید کنیم که بشه با پمپ کردن اون فهمید که زبان مستقل از متن نیست؟
۲- آیا تنها یک رشته متناقض کافی است؟ اگر بله آیا در این رشته فقط یک حالت بدست آوریم که نشان دهد W در زبان نیست کافی است؟ یا در زبانی که مطرح می کنیم باید تمام حالات را در نظر بگیریم و اگر در تمام حالات آن ما طوری پمپ کردیم آنوقت می گوییم زبان مستقل از متن نیست؟
با تشکر
هرکسی بتونه مسائل نظریه را با این لم حل کنه دیگه آخرشه . حل نویسنده کتاب لینز هم تبریک بهش میگه
ممنونم بابت سوال قشنگی که پرسیدین منم خودم هنوز جوابی پیدا نکردم ولی توضیحات زیر شاید کمکی بکنه(انصافا میتونه یه تست خوب باشه)
چون این الگوریتم در واقع یک مسابقه بین شما و حریف هست(رقابت)
باید تمام سعی خودمون رو انجام بدیم که حریف شکست بخوره نه اینکه با هم هماهنگ باشیم!
چون این سوالات تو هر لمی پیش میاد(منظم،مستقل،خطی...)
مثلا فرض کنیم یک زبان منظم aab*ccc داشته باشیم(مشخصه منظم)
حریف اگه m=10 انتخاب کنه
من هم xyz=aabbbbbbbbc در نظر میگیرم
حریف اینجوری میشکنه y=a z=bbbbbbbbc xy=aa |Y|>=1 |xy|<=m
حالا xy^iz به ازای هر i که در نظر بگیرم رشته ای حاصل میشه که جزء زبان نیست!؟
**ولی میدونیم زبان داده شده منظم دلیلی که به این نتیجه رسیدیم چون مثل مسابقه با هم بازی نکردیم، حریف میتونست شکستن رو بهتر انجام بده
اگه دوستان نظری دارن بگن؟
در این سوال بدون استفاده از لم پامپینگ هم میشه تشخیص به مستقل از متن نبودن زبان داد.
اگر a را در استک بریزم، بعد برای مقایسه a با b نیاز هست a از استک پاپ کنیم، c که میاد چون دیگه b نمونده و نمیتونستیم جایی ذخیرش کنیم امکان مقایسش وجود نداره، پس نمیتونه مستقل از متن باشه و با یه استک نمیشه.
اما لم پامپینگ:
به صورت یک مسابقه هست بین ما و حریف
ابتدا حریف یک عدد صحیح و مثبت m انتخاب میکند(در اثبات عکس نقیض لم توضیح داده شده که این m در واقع جمع سمت راست قواعد هست) حالا من باید رشته ای بگیرم به طول بزرگتر مساوی این تعداد(به دلیل تکراری که ممکن است بعضی رشته‌ها داشته باشند و باعث بشه از بعضی قواعد چند بار استفاده کنیم، شرط بزرگتر مساوی لحاظ شده) این رشته را به حریف میدیم، حال حریف باید این رشته را به ۵ زیر رشته uvxyz بشکنه، که البته در اینجا ما باید سخت ترین شرایطو برای خودمان در شکستن حریف در نظر بگیریم. به صورتیکه سه زیررشته میانی طول کمتر مساوی m داشته باشند و دو طرف x به صورت توام لاندا نباشند.
در این حالت ما باید همه حالاتی که ممکنه حریف این رشته را بشکند در نظر بگیریم، اگر تونستیم در تمامی آن حالات iی پیدا کنیم که رشته از زبان بیرون بیفته میشه گفت زبان مستقل از متنه
البته همه اینا بستگی داره که رشته اولیه را چطور انتخاب کنیم که با تمرین میشه مهارت کافیو بدست آورد.
و یادمون باشه که این لم برای اثبات مستقل از متن نبودن زبان به کار میره نه اثبات مستقل از متن بودن
(۲۸ آبان ۱۳۹۰ ۰۷:۰۰ ب.ظ)mahdikoochooloo نوشته شده توسط: من روی لم پمپ کار می کنم اما می بینم تناقضی هست. به عنوان مثال
{a^i .b^j. c^k: k>i , k>j}
در حل التمرینات لینز نوشته که ما W را a^m. b^m .c^m+1 می گیریم. خوب معلومه که این زبان مستقل از متن نیست. اما من یک حالت دیگه معرفی می کنم که مستقل از متن باشه مثلا
a^n.b^m.c^n+m
می بینیم که مستقل از متن شد.
رشته ای که در نظر گرفتین نمیتونه درست باشه، n مشخص نشده که چیه، باید حتما برحسب متغیری وابسته به m باشه.که بتونیم رشته هارو به صورت ۳ زیر رشته دربیاریم....
و نبایستی برای حریف شرایطو یه جوری فراهم کنیم که به نتیجه دلخواه خودمون برسیم که الان با فرض درستی این رشته، دقیقا شرایط برد حریفو مهیا کردیم.