موضوع مقاله: نظریه ماشین‌ها | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نظریه ماشین‌ها | مقدمه: در علوم نظری رایانه، نظریهٔ اتوماتا یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آن‌ها برای حل مسایل. | ## بخش 1: نظریه ماشین‌ها | یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود. تعاریف پایه نظریه ماشین‌ها شرح غیر قرار دادی یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده‌است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده‌است و به این حالت، حالت نهایی می‌گویند. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند. شرح قرار دادی واژگان نماد: کوچک‌ترین و بنیادی‌ترین موجودیتی که دارای معنی یا تأثیری بر ماشین است. ,z}=∑ و الفبای باینری {۰و۱}=∑ مثال‌هایی از الفبا هستند که بیشترین کاربرد را برای ما دارند. | ## بخش 2: نظریه ماشین‌ها | کلمه یا رشته: دنباله‌ای متناهی از نمادهای یک الفباست که با عمل الحاق به هم پیوسته‌اند. یک مثال از رشته به صورت مقابل است: w=aabc طول رشته با علامت |w| نمایش داده می‌شود و به تعداد نمادهای موجود در رشته گفته می‌شود. رشتهٔ تهی با نماد ε یا ℷ نمایش داده می‌شود و طول آن برابر صفر در نظر گرفته می‌شود. تعریف قراردادی ۵ تایی نمایندهٔ یک ماشین خودکار است که در آن: Q مجموعه‌ای از وضعیت هاست. ∑ یک مجموعهٔ کراندار از نشانه هاست که ما آن را الفبای زبانی که ماشین خودکار می‌پذیرد می‌نامیم. (بدیهی است که ) مجموعه‌ای از حالات است (برای مثال F⊆Q) که وضعیت‌های قبول نامیده می‌شوند. با داشتن حرف ورودی که می‌توان تابع‌گذار را به صورت نوشت؛ که این کار با استفاده از ترفند سادهٔ مالشcurrying صورت می‌گیرد. با داشتن یک جفت از حروف تابع جدید به صورت تعریف می‌شود که نشان دهندهٔ ترکیب توابع است. طبیعتاً، این فرایند می‌تواند به‌طور بازگشتی ادامه یابد و بنابراین یک تعریف بازگشتی از تابع داریم که برای تمام کلمات تعریف شده‌است و به شرح زیر است. این ساختار می‌تواند معکوس هم بشود، با داشتن ، می‌توان دوباره را ساخت و بنابراین، این دو توصیف هم ارزند. ماشین نیمه خودکار همان ماشین خودکار است با این تفاوت که وضعیت شروع و مجموعهٔ وضعیت‌های قبول آن نادیده گرفته شده‌اند. مفهوم‌های افزودهٔ وضعیت اولیه و وضعیت قبول باعث می‌شوند تا توانائی ماشین خودکار بیش از توانائی ماشین نیمه خودکار باشد، بدین شرح که ماشین نیمه خودکار نمی‌تواند یک زبان صوری را شناسائی کند. | ## بخش 3: نظریه ماشین‌ها | زبان که توسط ماشین خودکار کران‌دار پذیرفته شده‌است، این گونه تعریف می‌شود: زبان پذیرفته شدهٔ ماشین خودکار (یعنی ) مجموعه‌ای از کلمات است که با الفبای ساخته شده‌اند و وقتی به عنوان ورودی به ماشین خودکار داده می‌شوند، نهایتاً یکی از وضعیت‌های را نتیجه می‌دهند. زبان‌هایی را که توسط ماشین خودکار پذیرفته شده‌اند، زبان‌های قابل تشخیص می‌نامند. وقتی مجموعهٔ وضعیت‌های Q کران‌دار است، ماشین خودکار به عنوان ماشین خودکار کران‌دار شناخته می‌شود و مجموعهٔ همهٔ زبان‌های قابل تشخیص آن را، زبان‌های باقاعده می‌نامیم. در واقع یک هم‌ارزی قوی وجود دارد: به ازای هر زبان باقاعده یک ماشین خودکار وضعیت محدود وجود دارد. این ماشین خودکار، کلمه را در صورتی می‌پذیرد که حداقل یک مسیر از به وضعیتی از وجود داشته باشد. اگرگذار تعریف نشده باشد، ماشین نمی‌داند که چگونه به خواندن ورودی ادامه دهد و در نتیجه کلمه پذیرفته نمی‌شود. به این معنا که، اگر یک وضعیت گذارهای نامگذاری شده با ε را دارد، این ماشین می‌تواند در هر وضعیتی که به وسیلهٔ ε-گذار بدست آمده قرار گیرد که این کار می‌تواند با واسطه یا بدون واسطهٔ وضعیت‌های دیگر صورت گیرد. با این وجود می‌توان نشان داد که تمام این ماشین‌ها، می‌توانند زبان‌های مشابهی را بپذیرند. گسترهٔ ماشین‌های متناهی خانوادهٔ زبان‌هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. ماشین‌های خودکاری که از این ماشین‌ها به‌شمار می‌آیند، عبارتند از: ماشین‌های خودکار پشته‌ایpushdown automata(PDA) این ماشین‌ها همانند ماشین‌های خودکار کران‌دار قطعی (یا ماشین‌های خودکار کران‌دار غیر قطعی) هستند؛ با این تفاوت که حافظه را به صورت پشتهstack به دوش می‌کشند؛ و بنابراین تابع‌گذار نیز به نشانه‌ای که در بالای پشته قرار دارد وابسته است و همین تابع مشخص می‌کند که در هر گذار، پشته چگونه باید تغییر داده شود. این ماشین‌ها دارای یک حافظهٔ نامتناهی (به شکل یک نوار) و یک هد (که می‌تواند نوار را بخواند و تغییر دهد و در سرتاسر نوار در هر جهتی جابجا شود) هستند. ماشین‌های تورینگ با الگوریتم‌ها هم ارزند و پایهٔ نظری برای کامپیوترهای جدید می‌باشند. | ## جمع‌بندی | ماشین‌های تورینگ زبان‌های بازگشتی را می‌پذیرند و زبان‌های شمارش‌پذیر بازگشتی را شناسایی می‌کنند.