صفحهها: ۱ ۲
پاسخ سنجش هم شاید بر مبنای اون بوده.
اون حل پشته ای رو توی حل تمرین که در لینک زیر آمده ببینید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
در اون کلمه Remember داره از چه حافظه ای استفاده می کنه؟
finit control کجاست؟
این حافظه که میگید کجاست ؟ کدوم خطه من ندیدمش تو حل سیپسره ؟؟؟
ای کاش حل سیپسره زودتر گیر میاوردم چقدر عالی نوشته .
نوشتن ماشین پشته ای رو زیاد بلد نیستم. امیدوارم متوجه بشید:
ماشین ۳ تا حالت q0 و q1 و q2 داره که q0 حالت شروع و q2 حالت پایانیه. Z هم انتهای پشتمونه.
از q0 به q1 این حرکتهارو داریم:
[tex]\lambda,Z\to UVZ|VUZ[/tex]
از q1 به خودش با طوقه داریم:
[tex]\lambda,U\to aUa|aUb|bUa|bUb|a[/tex]
[tex]\lambda,V\to aUa|aUb|bUa|bUb|b[/tex]
[tex]a,a\to \lambda[/tex]
[tex]b,b\to \lambda[/tex]
[tex]\lambda,V\to aUa|aUb|bUa|bUb|b[/tex]
[tex]a,a\to \lambda[/tex]
[tex]b,b\to \lambda[/tex]
از q1 به q2 داریم:
[tex]\lambda,Z\to Z[/tex]
فکر کنم ماشینش همین باشه. دوتا رشته جدا ازهمه که هسته یکی a و هسته یکی b میشه. باید یه تعداد حرفو بخونید و به ازای هر حرف ۱ توی پشته پوش کنید. بعد یه a یا b رو بخونین. (فرض میکنیم a خونده باشیم. اگه b میخوندیم میشه با جابجایی حروف جوابو کامل کرد.) به تعداد ۱های درون پشته، حرف از ورودی میخونیم و اون ۱هارو پاپ میکنیم. دوباره یه تعداد حرف خونده و ۱ پوش میکنیم. اینبار حتماً باید b بخونیم (چون فرض کردیم دفعه قبل a خوندیم.) اگه حرف مذکور b بود و تعداد حروف باقی مونده از رشته با تعداد ۱های پشته برابر بود به حالت پایانی میریم.
بطور خلاصه دو رشته جدا ازهم رو باید شناسایی کنیم که حرف وسطشون متفاوت و مجموع طولشون با طول رشتمون برابره.
فکرکنم برای یه رشته طولانی که فقط یجا اختلاف وجود داره ماشین داغ کنه ولی جواب میده.
(۲۴ بهمن ۱۳۹۰ ۱۱:۲۲ ب.ظ)parimehraban نوشته شده توسط: این حافظه که میگید کجاست ؟ کدوم خطه من ندیمش تو حل سیپسره ؟؟؟دقیقا توی مورد سوم از لینکی هستش که گذاشتم.
(۲۴ بهمن ۱۳۹۰ ۱۱:۰۴ ب.ظ)sasanlive نوشته شده توسط:(24 بهمن ۱۳۹۰ ۱۰:۵۰ ب.ظ)Lakikharin نوشته شده توسط: S->UV|VU
U->aUa|bUa|aUb|bUb|a
V->aVa|bVa|aVb|bVb|b
این جواب تو همون حله سیپسره فکر کنم.
این گرامره عدم برابریه درسته؟
aabbbb \aaaaaa
این دو رشته طوله برابر دارن ولی متفاوتن باید بپذیره.
رشته اولو میتونه تولید کنه؟
منظورتون چیه؟ کدوم رشته؟ aabbbb رو که میشه تولید کرد. aabbbbaaaaaa رو هم میشه تولید کرد.
این سوال در هر دو کتاب لینز و سیپسر اومده:
سیپسر سوال ۲۳ فصل ۲
لینز تمرین ۱۰ از فصل ۱-۸ (البته به صورت 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 می کنیم و بعد از تمام شدن ورودی باید پشته خالی باشه.
(۲۴ بهمن ۱۳۹۰ ۱۱:۳۴ ب.ظ)sasanlive نوشته شده توسط:(24 بهمن ۱۳۹۰ ۱۱:۲۷ ب.ظ)Lakikharin نوشته شده توسط: منظورتون چیه؟ کدوم رشته؟ aabbbb رو که میشه تولید کرد.
با V باید تولید بشه درسته.
شما اشتقاق بدین ببینم میشه؟
S->UV
U->aUb
U->a
V->bVb
V->b
رشتمنون میشه aabbbb
رشته با 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 رو درنظر بگیرید. تعدادشون برابره ولی دو رشته با هم برابر نیستن. شرطش اینه که حداقل در یک مکان مشخص از رشته هامون ۲تا حرف متفاوت باشه. برای همین رشته رو دو قسمت متفاوت (طولشون لزوماً برابر نیست.) تقسیم میکنیم که حرفای وسطیشون که در یه مکان هستن با هم برابر نباشن.
(۲۵ بهمن ۱۳۹۰ ۰۶:۵۱ ب.ظ)Lakikharin نوشته شده توسط:(25 بهمن ۱۳۹۰ ۰۶:۰۵ ب.ظ)atharrashno نوشته شده توسط: چون گفتند مخالف هم باشند پس فقط کافیه
تعداد a های w1 با تعداد a های w2 برابر نباشه
وتعداد b های w1 با تعداد b های w2 برابر نباشه
نمیشه اینو گفت. ممکنه تعدادشون برابر باشه. aaba abaa رو درنظر بگیرید. تعدادشون برابره ولی دو رشته با هم برابر نیستن. شرطش اینه که حداقل در یک مکان مشخص از رشته هامون ۲تا حرف متفاوت باشه. برای همین رشته رو دو قسمت متفاوت (طولشون لزوماً برابر نیست.) تقسیم میکنیم که حرفای وسطیشون که در یه مکان هستن با هم برابر نباشن.
اتفا دقیقا بعد ارسال به همین نتیجه رسیدم اما نت قطع شد راه دوری نریمab ba هم عکسش ثابت میشه