صفحه‌ها: ۱ ۲
هوالعلیم
این زبان رو چطوری با یک پشته می شه حل کرد؟ مراحل پشته رو می خوام.
L=w1w2 ; |w1|=|w2| , w1#w2
w1 و w2 سیکما استارند.
متشکرم
این زبان مستقل از متن هست . اندازه w1 و w2 که برابر هست . در شرط هم که وابستگی وجود ندارد .
(۲۴ بهمن ۱۳۹۰ ۱۰:۰۶ ب.ظ)sasanlive نوشته شده توسط:(24 بهمن ۱۳۹۰ ۰۹:۴۳ ب.ظ)shervinrs نوشته شده توسط: در فایل ضمیمه (مسئله ۳)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
توضیح داده شده.
سوال بدی بوده. از اونا که سریع میزنی و مطمئنی درسته بعد ...
میتونین شکله ماشینشم بذارین.
به نظرم تو توضیحاتش داره از یه حافظه دیگه هم استفاده میکنه.
چون وقتی متناسب با w1 متغییر تو پشته میریزیم , متغییر های متناسب با حروف اول میرن ته پشته. چطوری درش میاره از ته پشته ؟
مگه برای پیاده سازی زبان مستقل از متن بجز پشته حافظه دیگه ای داریم؟
بعضی وقت‌ها از ماشین های دو پشته ای استفاده میکنیم در این صورت حتی اگه زبان وابسته به متن هم باشه میشه با این دو پشته ای‌ها مستقل از متن در نظر گرفت تو کتاب لینز در این مورد چند تا مثال حل کرده .
برابری اندازه w1 و w2 باپشته حله.
مشکل من تست عدم برابری خود اونهاست.
اگه دو پشته در نظر بگیریم که دیگه مستقل از متن نمی شه.
می شه این تمرینات لینز رو آدرس بدید تمرین چنده؟
البته می دونم که در مستقل از متن بودن این زبان شکی نیست. منتها پرسیدم تا درک بهتری داشته باشم. چون حدس می زنم که این تیپ سوال مد نظر طراح باشه.
(۲۴ بهمن ۱۳۹۰ ۱۰:۱۱ ب.ظ)parimehraban نوشته شده توسط: بعضی وقت‌ها از ماشین های دو پشته ای استفاده میکنیم در این صورت حتی اگه زبان وابسته به متن هم باشه میشه با این دو پشته ای‌ها مستقل از متن در نظر گرفت تو کتاب لینز در این مورد چند تا مثال حل کرده .
قدرت ماشینه دو پشته ای برابر ماشینه تورینگ هست.
پس اگه اینطور باشه همه زبانها رو با دو پشته پیاده سازی میکنیم. همه مستقل از متن میشن.
زبانی که با استفاده از یه پشته نشه پیاده سازی کرد مستقل از متن نیست.
ولی زبان مستقل از متنو میشه با استفاده از دو پشته هم پیاده سازی کرد.
یک سوال هم سال ۸۹ تقریبا مشابه این سوال اومده.
اونجا هم زده مستقل از متن.
اونجا هم جای بحث داره.
باید دقیقا بفهمم چطوریه ...
(۲۴ بهمن ۱۳۹۰ ۱۰:۲۱ ب.ظ)sasanlive نوشته شده توسط: قدرت ماشینه دو پشته ای برابر ماشینه تورینگ هست.
پس اگه اینطور باشه همه زبانها رو با دو پشته پیاده سازی میکنیم. همه مستقل از متن میشن.
زبانی که با استفاده از یه پشته نشه پیاده سازی کرد مستقل از متن نیست.
ولی زبان مستقل از متنو میشه با استفاده از دو پشته هم پیاده سازی کرد.
قدرت‌ها که برابر نیستند چون تورینگ زبانهای بیشتری را میپذیره و حافظه نامحدودی داره .
در مورد اینکه همه زبانها مستقل از متن میشه من هم وقتی این قسمت دوپشته ای‌ها خوندم واقعا گیج شدم گفتم این سودکمپ هم همه مسائل و مستقل از متن میبینه دقیقا این چیزی بود که به ذهن من هم رسید .
ولی باور کنید به فرض زبان زیر که وابسته به متن است با دو پشته ای به صورت مستقل از متن حلش کرده است.
a^nb^nc^nd^n
(۲۴ بهمن ۱۳۹۰ ۱۰:۲۴ ب.ظ)yaali نوشته شده توسط: یک سوال هم سال ۸۹ تقریبا مشابه این سوال اومده.
اونجا هم زده مستقل از متن.
اونجا هم جای بحث داره.
باید دقیقا بفهمم چطوریه ...
نه yaaali جان تو ۸۹ رشته دوم معکوسه. و معکوسو میشه چک کرد چون آخرین حرف متناسب با متغییر بالای پشته هست.
(۲۴ بهمن ۱۳۹۰ ۱۰:۲۷ ب.ظ)parimehraban نوشته شده توسط: قدرت‌ها که برابر نیستند چون تورینگ زبانهای بیشتری را میپذیره و حافظه نامحدودی داره .
در مورد اینکه همه زبانها مستقل از متن میشه من هم وقتی این قسمت دوپشته ای‌ها خوندم واقعا گیج شدم گفتم این سودکمپ هم همه مسائل و مستقل از متن میبینه دقیقا این چیزی بود که به ذهن من هم رسید .
ولی باور کنید به فرض زبان زیر که وابسته به متن است با دو پشته ای به صورت مستقل از متن حلش کرده است.
a^nb^nc^nd^n
اینکه قدرتشون برابره که اثبات شده هست و قضیه هست.
زبانی که میگین وابسته به متنه و میشه با دو پشته پیاده سازی کرد.گفتم قدرت ماشینه ۲ پشته ای برابر تورینگه و یه قضیه اثبات شده تا الان مگه اینکه شما نقضش کنین.
اوکی . گرفتم. توی ۸۹ چون رشته w1 همیشه آخرین حرفش بالای پشته است .موقع پاپ کردن می شه چک کرد که رشته دوم با معکوس رشته اول برابر هست یا نه.
ولی اینجا (۹۰) ابتدای رشته‌ی اول در دسترس نیست چون رفته ته پشته.
ولی خوب اون عکس ارسال ۹۵ از اون لینک بالا ظاهرا مال سیپسر هستش و این رو هم گفته مستقل از متنه. واسش گرامر هم توی اون لینک آورده . منتها من دقیقا نفهمیدم توی پشته چطوری کار می کنه.
جالب اینه که اگه w1=w2 بود در شرط زبان اونوقت مستقل از متن نبود.
گرامرشو که آقای parsaNA نوشته بود. فکر کنم بهتر باشه همون گرامرشو به ماشین پشته ای نامعین تبدیل کنیم. به نظرم اینکارو بکنیم بهتر باشه، چون نیازی نیست وسط رشته رو پیدا کنیم.
روش کارشم جالب بود. اگه از S->UV بریم تعداد حرف های جمع تعداد حرفهای قبل از هسته U و بعد از هسته V که به ترتیب a و b هستن میشه نصف طول رشتمون منهای یک. پس مکان این دو هسته در هرجای رشتمون بر حسب طول U و V باشن، یکی میشه. یعنی اگه طول رشتمون ۲n باشه و مکان هسته U رو با l مشخص کنیم که l از n بیشتر نیست، مکان هسته V میشه n+l که برابر نبودن این دو هسته میدونیم این دو رشته w1 و w2 حداقل در یک حرف در مکان lام باهم اختلاف دارن.
اینم گرامری که آقای parsaNA نوشتن:
S->UV|VU
U->aUa|bUa|aUb|bUb|a
V->aVa|bVa|aVb|bVb|b
بی زحمت با پشته بگین.
منظورم ترسیم PDA نیست.
همینطوری بصورت حرفی می خوام.
ببخشید من نتم قطع شد تو لینز رفتم دیدم نبود سیپسر دارم ولی حلشو ندارم .
(۲۴ بهمن ۱۳۹۰ ۱۱:۱۰ ب.ظ)parimehraban نوشته شده توسط: ببخشید من نتم قطع شد تو لینز رفتم دیدم نبود سیپسر دارم ولی حلشو ندارم .
سیپسر عکسش اینجا هست دیگه(ارساله ۹۵). موضوع همین سیپسره که گفته مستقل از متنه.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
شما هم دست رو چه سوالی گذاشتید اینو همه دو به شک هستند .