حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-19

حل تمرین 1-19

تمرین

یک تراگذار با حالت محدود یا بطور مخفف fst نوعی از اتوماتا متناهی معین است که فقط در مورد قبول یا رد شدن یک رشته تصمیم نمی گیرد. شکل‌های زیر، دیاگرام حالت دو تراگذار با حالت محدود به نام‌های T1 و T2 است.

در FST هر انتقال دو برچسب دارد ،که یکی مشخص کننده نماد ورودی و دیگری مشخص کننده نماد خروجی است. این نمادها توسط ممیز از یکدیگرجدا می شوند. در T1 انتقال از q1 به q2 با نماد ورودی 2 انجام شده و نماد خروجی 1 می‌باشد . بعضی از انتقالات ممکن است چندین ترکیب مختلف از ورودی و خروجی داشته باشد. مثلا در تراگذر T1از حالت q1 به خودش این مساله وجود دارد. هرگاه یک FST روی رشته ورودی W محاسباتی انجام دهد، نمادهای ورودی W1....Wn را نماد به نماد با شروع از حالت شروع، گرفته و انتقالات را متناسب با دنباله W1....Wn=W انجام می‌دهد. با هر انتقال، خروجی متناسب تولید می‌شود. به طور مثال ماشین T1 روی ورودی 2212011 دنباله حالتهای q1, q2,q2,q2,q2,q1,q1,q1 را دنبال کرده و خروجی 1111000 را تولید می‌کند . ماشین T2روی ورودی abbb خروجی 1011 را تولید می‌کند. برای هرکدام از رشته های ورودی زیر، دنباله حالت‌ها و خروجی را مشخص کنید.

الف-ماشین T1 روی ورودی011 .

ب-ماشین T1 روی ورودی 211.

پ-ماشین T1 روی ورودی0202 .

ت-ماشین T2 روی ورودیb .

ث-ماشین T2 روی ورودیbbab .

ج-ماشین T2 روی ورودی bbbbbb.

چ-ماشین T2 روی ورودی .

حل

الف:

011

دنباله حالت:q₁,q₁,q₁,q₁

خروجی:000

ب:

211

دنباله حالت:q₁,q₂,q₂,q₂

خروجی:111

پ:

0202

دنباله حالت:q₁,q₁,q₂,q₁,q₂

خروجی:0101

ت:

b

دنباله حالت:q₁,q₃

خروجی:1

ث:

bbab

دنباله حالت:q₁,q₃,q₂,q₃,q₂

خروجی:1111

ج:

bbbbbb

دنباله حالت:q₁,q₃,q₂,q₁,q₃,q₂,q₁
خروجی:110110

چ:

دنباله حالت:q₁

خروجی:تهی