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

حل تمرین ۱-۲۰

تمرین

تعریف غیر رسمی تراگذر با حالت محدود را در تمرین ۱-۱۹ مطالعه کنید. مشابه الگوی تعریف ۱-۱ کتاب یک تعریف رسمی برای این مدل ارائه دهید. فرض کنید که FST دارای الفبای ورودی Σ(سیگما) و الفبای خروجی Γ (گاما) بوده و نیاز به حالتهایی به عنوان پذیرش ندارد. این تعریف باید شامل تعریف رسمی محاسباتی که FST انجام می‌دهد نیز باشد. (راهنمایی: یک FST یک پنج تایی می‌باشد.توابع انتقال آن به شکل δ:Q×Σ→Q×Γ هستند.)

حل

تعریف رسمی FST

یک تراگذر متناهی (حالات محدود) یک پنج تایی (Q,Σ,Γ,δ,q_۰) است که:

۱- Q یک مجموعه محدود از الفبا (تصحیح شده: Q یک مجموعه محدود از حالات ماشین است!)

۲- Σ یک مجموعه از الفبای ورودی

۳- Γ مجموعه‌ای دیگر از الفبای خروجی

۴- δ:Q×Σ→Q×Γ تابع انتقال

۵- q_۰ حالت شروع

تعریف رسمی محاسبه:

یک FST متناهی (T=Q,Σ,Γ,δ,q_۰) را در نظر بگیرید که رشته W=w_۱ ,w_۲ ... w_n یک رشته ورودی است. آنگاه T متناسب با رشته W یک رشته خروجی M=m_۱ ,m_۲ ,....,m_n را تولید می‌کند اگر دنباله حالتهای r_۰,r_۱,..,r_n در Q موجود بوده و دارای شروط زیر باشد :

۱- r_۰=q_۰

۲- برای δ(r_i,w_i+۱)=(m_i+۱ ,r_i+۱ ) i=۰٬۱,۲,...

۳- هر m_i عضو مجموعه الفبای خروجی گاما(Γ) باشد.

نکته :

۱- به دلیل تفاوت الفبای ورودی با الفبای خروجی (تفاوت در نوع و تعداد اعضا) آنها را به طور جداگانه در تعریف رسمی ذکر کردیم.

۲- با توجه به آنکه در سوال ذکر شده‌است که نیازی به حالت پذیرش نداریم پس همواره مجموعه F که در تعریف آتوماتا وجود دارد تهی است و در تعریف رسمی یک FST ذکر نمی‌شود.