G1=منظم
G2=مستقل از متن
آیا مساله( L(G1)=L(G2 تصمیم پذیر است یا نه؟
مطمئن نیستم ولی فکر کنم بله تصمیم پذیره.
مطمئنم که تصمیم پذینیست
فصل آخر لینز توی تمریناش بود انگار
(۲۶ بهمن ۱۳۸۹ ۱۲:۱۷ ق.ظ)LALEH نوشته شده توسط: مطمئنم که تصمیم پذینیست
فصل آخر لینز توی تمریناش بود انگار
بود ولی حل شده نبود
تصمیم پذیر نیست. ساده ترین مثالش هم اینه که G1 رو بگیریم[tex]\sum^{\: \: \: \: \: \: \: \: \: \: *}[/tex]
نمی توان برابری هیچ دو زبان مسقل از متنی که حداقل یه دونشون منظم نیست رو جواب داد.
البته تعیین اینکه اشتراکشون تهی هست یا نه تصمیم پذیره!
راستی این مسئله یه استثنا داره، اونم زمانی هست که G1 تهی باشه...
عجب سوالی بود، فکر نمی کردن انقدر نکته دار باشه.
پست قبلی رو تصحیح می کنم. مسئله در حالت کلی تصمیم ناپذیره. اگر G1 متناهی باشه مسئله تصمیم پذیر میشه.
الگوریتم پاسخ به مسئله ای که تو پست اول گفته شده
با فرض این که G1 حتما منطم و G2 حتما نامنظم و مستقل از متنه)۱) بررسی می کنیم که آیا G1 متناهی است یا نه؟
۲) اگر نامتناهی بود مسئله تصمیم ناپذیره. اگر نبود بررسی می کنیم که آیا G2 متناهی هست یا نه؟
۳) اگر G2 هم متناهی بود، با یک روش معین (مثلا Backtrack) تمامی رشته های G1 و G2 را لیست می کنیم.
۴) حالا دیگه میشه مسئله رو جواب داد...
پس نتیجه می گیریم که یک مسئله توی حالت های خاص ممکنه تصمیم پذیر باشه.
یه نتیجه دیگه، اگه این مسئله که تو پست اول گفتید رو به یه ماشین بدیم، می تونه بهمون بگه که تصمیم پذیره یا نه...
یه نتیجه کلی اغلب این مستقل از متنها تو مسائل بدیهی تصمیم نا پذیرند به جز متناهی بودن و تهی بودن
برا منظما هم اکثرا تصمیم پذیرن
من از نمودار زیز مجموعهها اینا رو می حلم