پرش به محتوا

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

ویکی‎کتاب، کتابخانهٔ آزاد

حل تمرین ۱-۲۰

تمرین

[ویرایش]

تعریف غیر رسمی تراگذر با حالت محدود را در تمرین ۱-۱۹ مطالعه کنید. مشابه الگوی تعریف ۱-۱ کتاب یک تعریف رسمی برای این مدل ارائه دهید. فرض کنید که 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 ذکر نمی‌شود.