ل تمرین نظریه محاسبات/فصل اول/حل تمرین ۱-۲۰
حل تمرین ۱-۲۰
تمرین[ویرایش]
تعریف غیر رسمی تراگذر با حالت محدود را در تمرین ۱-۱۹ مطالعه کنید. مشابه الگوی تعریف ۱-۱ کتاب یک تعریف رسمی برای این مدل ارائه دهید. فرض کنید که FST دارای الفبای ورودی Σ(سیگما) و الفبای خروجی Γ (گاما) بوده و نیاز به حالتهایی به عنوان پذیرش ندارد. این تعریف باید شامل تعریف رسمی محاسباتی که FST انجام می‌دهد نیز باشد. (راهنمایی: یک FST یک پنج تایی می‌باشد.توابع انتقال آن به شکل δ:Q×Σ→Q×Γ هستند.)
حل[ویرایش]
تعریف رسمی FST
یک تراگذر متناهی (حالات محدود) یک پنج تایی (Q,Σ,Γ,δ,q۰) است که:
۱- Q یک مجموعه محدود از الفبا (تصحیح شده: Q یک مجموعه محدود از حالات ماشین است!)
۲- Σ یک مجموعه از الفبای ورودی
۳- Γ مجموعه‌ای دیگر از الفبای خروجی
۴- δ:Q×Σ→Q×Γ تابع انتقال
۵- q۰ حالت شروع
تعریف رسمی محاسبه:
یک FST متناهی (T=Q,Σ,Γ,δ,q۰) را در نظر بگیرید که رشته W=w۱ ,w۲ ... wn یک رشته ورودی است. آنگاه T متناسب با رشته W یک رشته خروجی M=m۱ ,m۲ ,....,mn را تولید می‌کند اگر دنباله حالتهای r۰,r۱,..,rn در Q موجود بوده و دارای شروط زیر باشد :
۱- r۰=q۰
۲- برای δ(ri,wi+۱)=(mi+۱ ,ri+۱ ) i=۰٬۱,۲,...
۳- هر mi عضو مجموعه الفبای خروجی گاما(Γ) باشد.
نکته :
۱- به دلیل تفاوت الفبای ورودی با الفبای خروجی (تفاوت در نوع و تعداد اعضا) آنها را به طور جداگانه در تعریف رسمی ذکر کردیم.
۲- با توجه به آنکه در سوال ذکر شده‌است که نیازی به حالت پذیرش نداریم پس همواره مجموعه F که در تعریف آتوماتا وجود دارد تهی است و در تعریف رسمی یک FST ذکر نمی‌شود.