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

1.25) تعریف غیررسمی مبدل متناهی الحالت (FST) داده شده در تمرین 1.24 را بخوانید و تعریفی رسمی برای این مدل ارایه دهید، با توجه به الگوی ارایه شده در تعریف 1.5 (صفحه 35 ). فرض کنید که هر FST یک الفبای ورودی به نام و یک الفبای خروجی به نام دارد اما حالت پذیرش ندارد. همچنین تعریفی رسمی از محاسبه ی FST ارایه دهید. (راهنمایی: هر FST یک پنج تایی است و تابع انتقال آن به صورت می باشد.)

Definition 1.5

A finite automaton is a 5-tuple (Q, Σ, ẟ, q0, F), where

  1. Q is a finite set called the states,
  2. Σ is a finite set called the alphabet,
  3. ẟ: Q × Σ ⟶ Q is the transition function,
  4. q0 is the start state, and
  5. FQ is the set of accept states.


با توجه به تعریف 1.5 داریم:

1)Q: مجموعه ی متناهی همه ی حالت های FST خواهد بود. مثلا: Q={q0,q1,q2}

2): مجموعه ی متناهی الفبای ورودی FST است.

3) مجموعه ی متناهی الفبای خروجی FST است.

4) < 5)

تعریف رسمی محاسبه ی FSA : می گوییم رشته ی W=w1 w2 ... wn ( خروجی FSA است اگر رشته ی Z=z1 z2 … zn و دنباله حالات R1, R2 … Rn+1 ( در دنباله می توانیم حالات تکراری داشته باشیم.مثلا:R3=R5=q0) موجود باشد که:

1)R1=q0 در حالت شروع باشد.

2)