‌ماشین‌ها

نویسنده: سید امیرعلی موسوی

فرض کنید تو یه مسابقه شرکت کردید و مجری به شما و رقیبتون می‌گه: «اول کار عدد ۱ به شما داده می‌شه. بعد از اون تو هر مرحله یه رقم، یا صفر یا یک، بهتون می‌دم و شما باید این رقم رو به سمت راست عددتون تو مرحله‌ی قبل اضافه کنید و بعد باقی‌مانده رو به ۷ اعلام کنید. تو هر مرحله هرکی زودتر این کارو بکنه امتیاز می‌گیره و بعد از ۱۰۱ مرحله هرکی بیشترین امتیاز رو بگیره برنده‌ی مسابقه‌ می‌شه.» حالا شما برای انجام همچین محاسباتی چه روشی رو انتخاب می‌کنید؟

یه روش ساده و دم‌دستی که وجود داره اینه که بیایم هر بار عددی که به دست می‌آد رو به ۷ تقسیم و باقی‌مانده رو اعلام کنیم. شاید این روش برای مراحل اولیه مناسب باشه ولی وقتی جلوتر بریم عدد اون مرحله، بزرگ و بزرگ‌تر می‌شه و این، فرایند محاسبات رو برای ما سخت‌تر می‌کنه.

حالا بیاید سعی کنیم یه جور دیگه به مسئله نگاه کنیم. فرض کنیم تو مرحله‌ی nام مسابقه هستیم و n-۱ رقم قبلی که تا مرحله‌ی اخیر داده شده (برای راحتی اسمش رو x می‌‌گذاریم) بر ۷ باقی‌مانده‌ی r داشته باشه. اگه در این مرحله مجری رقم a رو به ما بده، ما باید باقی‌مانده‌ی عدد xa رو حساب کنیم. اگه کمی دقت کنید، می‌بینید که این عدد رو می‌شه به شکل ۱۰x+a هم نوشت. عملاً این فرم به ما می‌گه که به‌جای باقی‌مانده‌ی xa بر ۷ می‌شه باقی‌مانده‌ی ۱۰r+a بر ۷ رو حساب کرد که محاسبه‌ی اون بسیار بسیار ساده‌تره و شما با این روش می‌تونید خیلی ساده محاسبات رو انجام بدید و تو مسابقه‌تون برنده بشید.

حالا که فهمیدید چجوری می‌شه تو همچین مسابقه‌ای راحت برد (مگه اصلاً فهمیدن همچین چیزی تو این دوره‌زمونه اهمیتی داره-ـ-) بیایم به اتفاقاتی که در حل این مسئله رخ می‌ده کمی توجه کنیم. همون طور که می‌بینید، ما در اینجا به‌جای اینکه بیایم کل عدد رو در هر مرحله در نظر بگیریم فقط باقی‌مانده‌ی اون رو در نظر می‌گیریم و هربار که مجری عدد جدید رو بگه ما تغییرات لازم رو اعمال می‌کنیم؛ انگار که ۷ حالت داشته باشیم (۰، ۱، . . . ، ۶) و هر بار بین این حالت‌ها جابه‌جا بشیم.

حالا به شکل زیر دقت کنید:

همون طور که می‌بینید شکل بالا دقیقا کاری رو که ما در این مسابقه داریم انجام می‌دیم نمایش می‌ده؛ یعنی اگه در مرحله‌ای باقی‌مانده مثلاً عدد ۴ باشه، اگه مجری به ما عدد ۰ بده، باقی‌مانده به ۵ تغییر می‌کنه و اگه به ما عدد ۱ بده، باقی‌مانده به عدد ۶ تغییر می‌کنه و همون طور که در شکل معلومه، از دایره‌ی شماره‌ی ۴ با فلش‌های ۰ و ۱ به دایره‌های ۵ و ۶ می‌ریم.

حالا این شکل به چه دردی می‌خوره؟ این ساختار دایره‌ و فلش‌ها که در بالا می‌بینیم یکی از ساختار‌های ابتدایی برای طراحی ماشین‌هاییه که برای ما محاسبات انجام می‌دن و بهشون Deterministic Finite Automata یا به اختصار DFA می‌گیم. در این‌گونه ماشین‌ها، ورودی کاراکتربه‌کاراکتر به ماشین داده می‌شه (مثل بالا که مجری رقم‌به‌رقم اعداد رو به ما می‌داد) و بعد از اینکه ورودی کامل داده شه، می‌شه نتیجه رو مشاهده کرد.

اما حالا به هر شکلی با دایره و فلش DFA می‌گیم؟

خیر. برای اینکه شکل ما یک DFA باشد لازمه شروط زیر رو داشته باشه:

۱.‌ مجموعه‌ی کاراکتر‌ها متناهی باشه: در اینجا همون {۰,۱} است.

۲. مجموعه‌ی همه‌ی حالت‌ها متناهی باشه: منظور از حالت، همون دایره‌ها در شکله که اینجا ۷ دایره داریم.

۳. دقیقاً یک حالت اولیه داشته باشیم: حالت اولیه، دایره‌ایه که اول کار، وقتی کاراکتر‌های ورودی‌ مسئله به ماشین داده نشده، در اون قرار داریم. در این‌جا چون اول کار عدد ما ۱ بود پس حالت اولیه‌ی ما همون دایره‌ی ۱ است.

۴. از هر حالت با هر کاراکتر دقیقاً به یک حالت بشه رفت.

۵. حالات نهایی مشخص و زیرمجموعه‌ی همه‌‌ی حالات باشند.

احتمالاً این سوال براتون به وجود اومده که اصلاً حالات نهایی چی هستن؟ باید به شما بگم که در نظریه‌ی زبان‌ها و اتوماتا (حوزه‌ای که در اون به ساختار این‌گونه اتوماتاها یا همون ماشین‌ها می‌پردازن) فرض می‌شه مسائلی که می‌خواهیم برای اونا ماشین طراحی کنیم از جنس پرسش‌های بله/خیر هستن و این باور وجود داره که اگه ما این‌گونه مسائل رو حل کنیم، انگار همه‌ی مسائل دیگه حل ‌می‌شه. برای درک بهتر، همین مسئله‌ی بالا یعنی همون مسئله‌ی «باقی‌مانده‌ی اعداد با ارقام ۰ و ۱ به ۷» رو در نظر بگیرید. اگه پرسش رو به این شکل تغییر بدیم که «آیا باقی‌مانده‌ی عدد بر ۷ برابر iهست؟» و برای هر i یک ماشین بسازیم، این ۷ ماشین، هم‌زمان به ما کمک می‌کنن تا مسئله‌ی اول رو حل کنیم. خلاصه که ماشین‌هایی که ما طراحی ‌می‌کنیم قراره به ما جواب بله یا خیر بدن و این کار رو با استفاده از حالات نهایی انجام می‌دن. در ساختار DFAها بعضی از حالات (یا همون دایره‌ها) به عنوان حالات نهایی مشخص می‌شن. اگه یادتون باشه گفتیم که این ماشین‌ها ورودی رو کاراکتربه‌کاراکتر دریافت می‌کنن و همون طور که ما در مسابقه بین حالت‌ها جا‌به‌جا می‌شدیم، ماشین‌ها هم بعد از دریافت هر کاراکتر با توجه به فلش‌ها بین حالات جا‌به‌جا می‌شن. وقتی ماشین‌ آخرین کاراکتر رو دریافت کنه و با دریافت اون مثلاً در حالتی به اسم q قرار بگیره، اگه حالت q یک حالت نهایی باشه، جواب بله و در غیر این صورت جواب خیر می‌ده.

برای مثال به شکل زیر دقت کنید و سعی کنید متوجه بشید که این DFA که رشته‌هایی با کاراکترهای ۰ و ۱ می‌گیره در چه صورت جواب بله ‌می‌ده (حالت یک که با دو دایره نمایش داده شده به‌معنی حالت نهاییه).

راهنمایی: به تعداد یک‌ها توجه کنید. یادتون باشه که جواب‌تون رو با رستا اینفو (@rastaiha_info) به اشتراک بذارید.

حالا که با ساختار DFA آشنا شدید شاید بد نباشه این رو هم بدونید که این نوع ماشین‌ها، ماشین‌های ساده‌ای هستند و مسائل بسیار زیادی وجود داره که نمی‌شه با DFA حلشون کرد. برای همین ریاضی‌دانا روی ساختار‌های دیگه‌ای هم کار کردند. تا اینکه شخصی به نام آلن تورینگ ساختاری به نام ماشین تورینگ طراحی کرد و ثابت کرد که این ساختار قوی‌ترین است؛ هر ماشینی اگه بتونه مسئله‌ای رو حل کنه، ماشین تورینگ هم اونو حل ‌می‌کنه. در نهایت جالبه بدونید اکثر ماشین‌های امروزی مثل کامپیوتر‌ها، موبایل‌ها و . . . نمونه‌ی پیشرفته‌تر همین ماشین تورینگ هستن.