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

1.24) یک " ماشین مبدل حالات " (FST) یک نمونه از یک DFA است که خروجی آن به جای پذیرش یا عدم پذیرش ، یک رشته است. تصاویر زیر دو نمونه از FST با نام های T1 و T2 است :

هر انتقال در یک FST توسط دو نماد نشان داده می شود ، یکی برای نماد ورودی و دیگری برای نماد خروجی. این دو نماد توسط یک / از هم جدا می شوند. مثلا در ماشین T1 انتقال از q1 به q2 دارای نماد رودی 2 و نماد خروجی 1 است. ممکن است بعضی از انتقالات شامل چند ورودی و چند خروجی باشنذ مانند انتقال از q1 به خودش در ماشین T1. وقتی یک FST روی رشته ی ورودی w محاسبه انجام می دهد، نمادهای wn ...w2 , w1 را یک به یک می خواند و با شروع از حالت آغازین با حرکت از روی انتقالات ، متناسب با نماد خوانده شده ، هر دفعه از روی یک انتقال عبور می کند و نماد خروجی را اعلام می نماید. مثلا هنگام محاسبه روی رشته 2212011 ، ماشین T1 وارد حالات q1,q1,q1,q2,q2,q2,q2,q1 می شودو خروجی 1111000 را تولید می کند و ماشین T2 نیز برای ورودی abbb خروجی 1011 را تولید می کند. برای هر یک از ورودی های داده شده در زیر ، ترتیب حالات وارد شده و خروجی تولید شده را محاسبه کنید : الف) T1 با ورودی 011 ب) T1 با ورودی 211 ج)T1 با ورودی 121 د)T1 با ورودی 0202 ه)T2 با ورودی b و)T2 با ورودی bbab ز)T2 با ورودی bbbbbb ح)T2 با ورودی e

حل ) a)states :=q1,q1,q1,q1 output:=000 b)states :=q1,q2,q2,q2 output:=111 c)states :=q1,q1,q2,q2 output:=011 d)states :=q1,q1,q2,q1,q2 output:=0101 e)states :=q1,q3 output:=1 f)states :=q1,q3,q2,q3,q2 output:=1111 g)states :=q1,q3,q2,q1,q3,q2,q1 output:=110110 h)states :=q1 output:=e