این سوال در هر دو کتاب لینز و سیپسر اومده:
سیپسر سوال ۲۳ فصل ۲
لینز تمرین ۱۰ از فصل ۱-۸ (البته به صورت w1cw2 هست)

من چیزی رو که از اون PDF می فهمم رو می نویسم (ترجمه می کنم). (چون خودمم نرفتم دنبالش که بفهمم دقیقا چجوریه)
فرض کنید که رشته ما به صورت W = XY هست. (که اندازه X و Y برابر)
این رشته تنها در صورتی عضو زبان ماست که اندازه W زوج باشه و کافیه که تنها یک i وجود داشته باشه که به ازای اون Xi <> Yi باشه. مسئله اصلی حدس محل i است. می تونید ببینید که اگر اندازه X و Y با هم برابر باشد، تعداد حروفی که از Xi+1 تا Yi داریم برابر بقیه حروف موجود در W است. (با مثال برای یک رشته با طول زوج این رو می تونید ببینید)
حالا PDA ما برای تشخیص زبان، محلی در X و محلی در Y رو حدس میزنه و با استفاده از پشته تشخیص میده که تعداد حروفی که در این فاصله هست با بقیه تعداد حروف برابر یا نه.
نکته اساسی اینه که پس ماشین کجا حرف Xi رو نگه داره تا بعدا با Yi مقایسه کنه. طبق حل گفته شده که در محل i‌ام باید:
Remember the current input symbol in the finite control
این جمله به نظر من یعنی این:
یعنی چون [tex]x, y \in (0,1)^*[/tex] هست و ما فقط یک حرف (از دو نوع حرف موجود) رو می خوایم به خاطر بسپاریم، می تونیم در قواعد PDA در صورتی که Xi حرف ۰ بود (مثلا) به حالت q3 بریم و اگر حرف ۱ بود به حالت q4 بریم و به این صورت با استفاده از قواعد حرف Xi رو به خاطر بسپاریم. بعد ماشین جای Yi رو باید حدس بزنه و با توجه به اینکه از q3 به اینجا رسیده باشیم یا از q4 باید در محل حدس زده شده از رشته Yi حرف ۰ یا ۱ داشته باشیم.
قبل از Xi حرف‌ها باید در پشته Push بشه و از اون به بعد Pop میکنیم تا پشته خالی بشه و بعد دوباره Push میکنیم تا محل Yi. بعد Yi نسبت به حالتی که از Xi تا اینجا اومدیم باید با Xi یکی نباشه. از اینجا به بعد Pop می کنیم و بعد از تمام شدن ورودی باید پشته خالی باشه.

این زبان مستقل از متن هست . اندازه w1 و w2 که برابر هست . در شرط هم که وابستگی وجود ندارد .

---

(۲۴ بهمن ۱۳۹۰ ۱۰:۰۶ ب.ظ)sasanlive نوشته شده توسط:  

(24 بهمن ۱۳۹۰ ۰۹:۴۳ ب.ظ)shervinrs نوشته شده توسط:  در فایل ضمیمه (مسئله ۳)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
توضیح داده شده.
سوال بدی بوده. از اونا که سریع میزنی و مطمئنی درسته بعد ...

میتونین شکله ماشینشم بذارین.
به نظرم تو توضیحاتش داره از یه حافظه دیگه هم استفاده میکنه.
چون وقتی متناسب با w1 متغییر تو پشته میریزیم , متغییر های متناسب با حروف اول میرن ته پشته. چطوری درش میاره از ته پشته ؟
مگه برای پیاده سازی زبان مستقل از متن بجز پشته حافظه دیگه ای داریم؟

بعضی وقت‌ها از ماشین های دو پشته ای استفاده میکنیم در این صورت حتی اگه زبان وابسته به متن هم باشه میشه با این دو پشته ای‌ها مستقل از متن در نظر گرفت تو کتاب لینز در این مورد چند تا مثال حل کرده .

(۲۴ بهمن ۱۳۹۰ ۱۰:۱۱ ب.ظ)parimehraban نوشته شده توسط:  بعضی وقت‌ها از ماشین های دو پشته ای استفاده میکنیم در این صورت حتی اگه زبان وابسته به متن هم باشه میشه با این دو پشته ای‌ها مستقل از متن در نظر گرفت تو کتاب لینز در این مورد چند تا مثال حل کرده .

قدرت ماشینه دو پشته ای برابر ماشینه تورینگ هست.
پس اگه اینطور باشه همه زبانها رو با دو پشته پیاده سازی میکنیم. همه مستقل از متن میشن.
زبانی که با استفاده از یه پشته نشه پیاده سازی کرد مستقل از متن نیست.
ولی زبان مستقل از متنو میشه با استفاده از دو پشته هم پیاده سازی کرد.

برابری اندازه w1 و w2 باپشته حله.
مشکل من تست عدم برابری خود اونهاست.

اگه دو پشته در نظر بگیریم که دیگه مستقل از متن نمی شه.

می شه این تمرینات لینز رو آدرس بدید تمرین چنده؟

البته می دونم که در مستقل از متن بودن این زبان شکی نیست. منتها پرسیدم تا درک بهتری داشته باشم. چون حدس می زنم که این تیپ سوال مد نظر طراح باشه.

یک سوال هم سال ۸۹ تقریبا مشابه این سوال اومده.
اونجا هم زده مستقل از متن.
اونجا هم جای بحث داره.
باید دقیقا بفهمم چطوریه ...

(۲۴ بهمن ۱۳۹۰ ۱۰:۲۴ ب.ظ)yaali نوشته شده توسط:  یک سوال هم سال ۸۹ تقریبا مشابه این سوال اومده.
اونجا هم زده مستقل از متن.
اونجا هم جای بحث داره.
باید دقیقا بفهمم چطوریه ...

نه yaaali جان تو ۸۹ رشته دوم معکوسه. و معکوسو میشه چک کرد چون آخرین حرف متناسب با متغییر بالای پشته هست.

اوکی . گرفتم. توی ۸۹ چون رشته w1 همیشه آخرین حرفش بالای پشته است .موقع پاپ کردن می شه چک کرد که رشته دوم با معکوس رشته اول برابر هست یا نه.

ولی اینجا (۹۰) ابتدای رشته‌ی اول در دسترس نیست چون رفته ته پشته.

ولی خوب اون عکس ارسال ۹۵ از اون لینک بالا ظاهرا مال سیپسر هستش و این رو هم گفته مستقل از متنه. واسش گرامر هم توی اون لینک آورده . منتها من دقیقا نفهمیدم توی پشته چطوری کار می کنه.

جالب اینه که اگه w1=w2 بود در شرط زبان اونوقت مستقل از متن نبود.

بی زحمت با پشته بگین.
منظورم ترسیم PDA نیست.
همینطوری بصورت حرفی می خوام.

ببخشید من نتم قطع شد تو لینز رفتم دیدم نبود سیپسر دارم ولی حلشو ندارم .

(۲۴ بهمن ۱۳۹۰ ۱۱:۱۰ ب.ظ)parimehraban نوشته شده توسط:  ببخشید من نتم قطع شد تو لینز رفتم دیدم نبود سیپسر دارم ولی حلشو ندارم .

سیپسر عکسش اینجا هست دیگه(ارساله ۹۵). موضوع همین سیپسره که گفته مستقل از متنه.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

شما هم دست رو چه سوالی گذاشتید اینو همه دو به شک هستند .

پاسخ سنجش هم شاید بر مبنای اون بوده.

اون حل پشته ای رو توی حل تمرین که در لینک زیر آمده ببینید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.



در اون کلمه Remember داره از چه حافظه ای استفاده می کنه؟
finit control کجاست؟

این حافظه که میگید کجاست ؟ کدوم خطه من ندیدمش تو حل سیپسره ؟؟؟
ای کاش حل سیپسره زودتر گیر میاوردم چقدر عالی نوشته .

نوشتن ماشین پشته ای رو زیاد بلد نیستم. امیدوارم متوجه بشید:
ماشین ۳ تا حالت q0 و q1 و q2 داره که q0 حالت شروع و q2 حالت پایانیه. Z هم انتهای پشتمونه.

از q0 به q1 این حرکتهارو داریم:


از q1 به خودش با طوقه داریم:


از q1 به q2 داریم:


فکر کنم ماشینش همین باشه. دوتا رشته جدا ازهمه که هسته یکی a و هسته یکی b میشه. باید یه تعداد حرفو بخونید و به ازای هر حرف ۱ توی پشته پوش کنید. بعد یه a یا b رو بخونین. (فرض میکنیم a خونده باشیم. اگه b میخوندیم میشه با جابجایی حروف جوابو کامل کرد.) به تعداد ۱های درون پشته، حرف از ورودی میخونیم و اون ۱هارو پاپ میکنیم. دوباره یه تعداد حرف خونده و ۱ پوش میکنیم. اینبار حتماً باید b بخونیم (چون فرض کردیم دفعه قبل a خوندیم.) اگه حرف مذکور b بود و تعداد حروف باقی مونده از رشته با تعداد ۱های پشته برابر بود به حالت پایانی میریم.
بطور خلاصه دو رشته جدا ازهم رو باید شناسایی کنیم که حرف وسطشون متفاوت و مجموع طولشون با طول رشتمون برابره.
فکرکنم برای یه رشته طولانی که فقط یجا اختلاف وجود داره ماشین داغ کنه ولی جواب میده.

(۲۴ بهمن ۱۳۹۰ ۱۱:۲۲ ب.ظ)parimehraban نوشته شده توسط:  این حافظه که میگید کجاست ؟ کدوم خطه من ندیمش تو حل سیپسره ؟؟؟

دقیقا توی مورد سوم از لینکی هستش که گذاشتم.

رشته با U شروع میشه. S->UV و U به aab و V به bbb تبدیل میشه.
میشه اینجوری هم گفت که U به a و V به abbbb تبدیل میشه. فقط باید وسط دوتا رشتمون تفاوت داشته باشه که به جواب برسیم.

گفتم که لزومی نداره طول U با V برابر بشن. اگه منظورتون تولید aabbbbaaaaaa باشه میشه:
S->VU و V=aabbb و U=baaaaaa. مسلماً اینارو میشه تولید کرد.

چون گفتند مخالف هم باشند پس فقط کافیه
تعداد a های w1 با تعداد a های w2 برابر نباشه
وتعداد b های w1 با تعداد b های w2 برابر نباشه

خوب میشه به راحتی پشته ایو طراحی کرد اما خدایش احسنت به طراح سوال خوشکلی بود

(۲۵ بهمن ۱۳۹۰ ۰۶:۰۵ ب.ظ)atharrashno نوشته شده توسط:  چون گفتند مخالف هم باشند پس فقط کافیه
تعداد a های w1 با تعداد a های w2 برابر نباشه
وتعداد b های w1 با تعداد b های w2 برابر نباشه

نمیشه اینو گفت. ممکنه تعدادشون برابر باشه. aaba abaa رو درنظر بگیرید. تعدادشون برابره ولی دو رشته با هم برابر نیستن. شرطش اینه که حداقل در یک مکان مشخص از رشته هامون ۲تا حرف متفاوت باشه. برای همین رشته رو دو قسمت متفاوت (طولشون لزوماً برابر نیست.) تقسیم میکنیم که حرفای وسطیشون که در یه مکان هستن با هم برابر نباشن.