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

1.25) تعریف غیررسمی مبدل متناهی الحالت (FST) داده شده در تمرین 1.24 را بخوانید و تعریفی رسمی برای این مدل ارایه دهید، با توجه به الگوی ارایه شده در تعریف 1.5 (صفحه 35 ). فرض کنید که هر FST یک الفبای ورودی به نام و یک الفبای خروجی به نام دارد اما حالت پذیرش ندارد. همچنین تعریفی رسمی از محاسبه ی FST ارایه دهید. (راهنمایی: هر FST یک پنج تایی است و تابع انتقال آن به صورت $Q\times \mathrm{\Sigma }\to Q\times \mathrm{\Gamma }$ می باشد.)

Definition 1.5

A finite automaton is a 5-tuple (Q, Σ, ẟ, q₀, 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. q₀ is the start state, and
5. F ⊆ Q is the set of accept states.

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

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

2)$\mathrm{\Sigma }$: مجموعه ی متناهی الفبای ورودی FST است.

3) $\mathrm{\Gamma }$ مجموعه ی متناهی الفبای خروجی FST است.

4) <$\delta :Q\times \mathrm{\Sigma }\to Q\times \mathrm{\Gamma }$ 5)$q_0\in Q$

تعریف رسمی محاسبه ی FSA : می گوییم رشته ی W=w1 w2 ... wn ( $\mathrm{\forall }i\in \{1,2,\dots ,n\}(wi\in \mathrm{\Gamma })$ خروجی FSA است اگر رشته ی Z=z1 z2 … zn $\mathrm{\forall }i\in \{1,2,\dots ,n\}(zi\in \mathrm{\Sigma })$ و دنباله حالات R1, R2 … Rn+1 ( $\mathrm{\forall }i\in \{1,2,\dots ,n+1\}(Ri\in Q)$ در دنباله می توانیم حالات تکراری داشته باشیم.مثلا:R3=R5=q0) موجود باشد که:

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

2) $\mathrm{\forall }i\in \{1,2,\dots ,n\}(\delta (Ri,zi)=(R(i+1),wi)$