حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۵۰

سوال:

تعریف غیر رسمی ماشین مبدل حالات (FST) را در تمرین 1.24 مطالعه کرده و ثابت کنید که هیچ FST ای نمی تواند خروجی w^R را برای ورودی w تولید کند (اگر الفبای ورودی و خروجی {0, 1} باشند)

پاسخ:

اگر یک FST داشته باشیم که به ازای ورودی w خروجی w^R را تولید کند, در این صورت خروجی مربوط به حرف اول باید با حرف آخر رشته ی ورودی برابر باشد و این در حالی است که حرف اول خروجی پیش از آمدن حرف آخر ورودی مشخص می شود. اگر دو رشته ای را به عنوان ورودی FST در نظر بگیریم که حرف اول آنها یکسان و حرف آخر آنها متفاوت باشد در این صورت چون حرف اول آنها یکسان است پس حرف اول خروجی آنها نیز یکسان است و چون حرف آخر آنها متفاوت است پس حرف اول خروجی آنها باید متفاوت باشد و این تناقض است, پس هیچ FST ای نمیتواند برای هر رشته ی w خروجی w^R را تولید کند.