راستی این مسئله یه استثنا داره، اونم زمانی هست که G1 تهی باشه...
عجب سوالی بود، فکر نمی کردن انقدر نکته دار باشه.

پست قبلی رو تصحیح می کنم. مسئله در حالت کلی تصمیم ناپذیره. اگر G1 متناهی باشه مسئله تصمیم پذیر میشه.
الگوریتم پاسخ به مسئله ای که تو پست اول گفته شده

با فرض این که G1 حتما منطم و G2 حتما نامنظم و مستقل از متنه)
۱) بررسی می کنیم که آیا G1 متناهی است یا نه؟
۲) اگر نامتناهی بود مسئله تصمیم ناپذیره. اگر نبود بررسی می کنیم که آیا G2 متناهی هست یا نه؟
۳) اگر G2 هم متناهی بود، با یک روش معین (مثلا Backtrack) تمامی رشته های G1 و G2 را لیست می کنیم.
۴) حالا دیگه میشه مسئله رو جواب داد...
پس نتیجه می گیریم که یک مسئله توی حالت های خاص ممکنه تصمیم پذیر باشه.
یه نتیجه دیگه، اگه این مسئله که تو پست اول گفتید رو به یه ماشین بدیم، می تونه بهمون بگه که تصمیم پذیره یا نه...