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

1.25) تعریف غیررسمی مبدل متناهی الحالت (FST) داده شده در تمرین 1.24 را بخوانید و تعریفی رسمی برای این مدل ارایه دهید، با توجه به الگوی ارایه شده در تعریف 1.5 (صفحه 35 ). فرض کنید که هر FST یک الفبای ورودی به نام و یک الفبای خروجی به نام دارد اما حالت پذیرش ندارد. همچنین تعریفی رسمی از محاسبه ی FST ارایه دهید. (راهنمایی: هر FST یک پنج تایی است و تابع انتقال آن به صورت $Q\times \Sigma \to Q\times \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)$\Sigma$: مجموعه ی متناهی الفبای ورودی FST است.

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

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

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

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

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