نظریه ماشین‌ها

در علوم نظری رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آن‌ها برای حل مسائل. به این ماشین‌های انتزاعی اتوماتا گفته می‌شود. این نظریه بسیار نزدیک به نظریهٔ زبان صوری است، به‌طوری‌که اتوماتا اغلب توسط دستهٔ زبان‌های رسمی قابل تشخیص دسته‌بندی می‌شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می‌کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان‌های فرمال هستند.

توضیحات پایه

مثالی از اتوماتا و مطالعه خصوصیات ریاضی چنین اتوماتونی نظریه اتوماتا است.

یک ماشین، یک مدل ریاضی از ماشین حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.

به صورت کلی، یک ماشین شامل مجموعه‌ای متناهی یا شماری از حالات مختلف است.

تعاریف پایه نظریه ماشین‌ها

شرح غیر قراردادی

یک ماشین خودکار قرار است که بر روی تعدادی ورودی از دنباله یا رشته در مراحل زمانی گسسته اجرا شود. در هر مرحله از زمان، ماشین یک ورودی که از مجموعه‌ای از نمادها یا حرف‌ها برداشته شده است را، می‌گیرد که به آن الفبا (Alphabet) گفته می‌شود. یک ماشین حاوی مجموعهٔ متناهی از حالت‌هاست. در هر لحظه از اجرا بسته به نوع ماشین، می‌تواند در یکی یا چند تا از حالت‌هایش باشد. در هر مرحلهٔ زمانی، هنگامی که ماشین یک نماد را می‌خواند، بر اساس حالت فعلی و نماد خوانده شده به حالت بعدی پرش یا گذر می‌کند. این تابع روی حالت فعلی و نماد ورودی تابع‌گذار گفته می‌شود. ماشین تا زمانی که یک ورودی کامل خوانده شود ورودی را نماد به نماد در دنباله‌ای می‌خواند و از حالتی به حالت دیگر بر اساس تابع گذار، گذر می‌کند. زمانی که ورودی نهایی خوانده می‌شود، اصطلاحاً ماشین متوقف شده است و به این حالت، حالت نهایی می‌گویند. بر اساس حالت نهایی گفته می‌شود که ماشین یک ورودی را قبول یا رد کرده است. زیر مجموعه‌ای از حالت‌های ماشین وجود دارد که به عنوان مجموعهٔ حالت‌های مورد قبول تعریف می‌شود. اگر حالت نهایی یک حالت مورد قبول باشد ماشین ورودی را پذیرفته است. در غیر این صورت ورودی رد می‌شود. به مجموعه‌ای از ورودی‌ها که توسط ماشین پذیرفته می‌شود زبان قابل تشخیص ماشین می‌گویند.

شرح قراردادی

واژگان

• نماد: کوچک‌ترین و بنیادی‌ترین موجودیتی که دارای معنی یا تأثیری بر ماشین است. برخی مواقع به نمادها حرف هم گفته می‌شود.
• الفبا: یک مجموعه غیر تهی و متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود. همچنین به هر نماد الفبا یک حرف گفته می‌شود. به عنوان مثال، الفبای لاتین {a,b،c,... ,z}=∑ و الفبای باینری {۰ و ۱}=∑ مثال‌هایی از الفبا هستند که بیشترین کاربرد را برای ما دارند.
• کلمه یا رشته: دنباله‌ای متناهی از نمادهای یک الفباست که با عمل الحاق به هم پیوسته‌اند. به عنوان مثال فارسی یک رشته روی الفبای زبان فارسی است. یک مثال از رشته به صورت مقابل است: w=aabc

طول رشته با علامت |w| نمایش داده می‌شود و به تعداد نمادهای موجود در رشته گفته می‌شود. رشتهٔ تهی با نماد ε یا ℷ نمایش داده می‌شود و طول آن برابر صفر در نظر گرفته می‌شود. به عنوان مثال اگر w=abcc آنگاه: ۴=|w|

• زبان: مجموعه‌ای از رشته‌ها است. این مجموعه می‌تواند متناهی یا نامتناهی باشد.

تعریف قراردادی

۵ تایی $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ نمایندهٔ یک ماشین خودکار است که در آن:

• Q مجموعه‌ای از وضعیت‌هاست.
• ∑ یک مجموعهٔ کراندار از نشانه‌هاست که ما آن را الفبای زبانی که ماشین خودکار می‌پذیرد می‌نامیم.
• δ تابع‌گذار است که

$\delta :Q\times \Sigma \rightarrow Q.$

(برای ماشین خودکار غیر قطعی، یک رشتهٔ خالی نیز یک ورودی قابل قبول است)

• $q_{0}$ وضعیت شروع است، یعنی وضعیتی از ماشین خودکار که در آن وضعیت، هیچ‌یک از ورودی‌ها هنوز پردازش نشده است. (بدیهی است که $q_{0}\in Q$)
• $F$ مجموعه‌ای از حالات $Q$ است (برای مثال F⊆Q) که وضعیت‌های قبول نامیده می‌شوند.

با داشتن حرف ورودی $a$ که $a\in \Sigma$ می‌توان تابع‌گذار را به صورت $\delta _{a}:Q\rightarrow Q$ نوشت؛ که این کار با استفاده از ترفند سادهٔ مالش صورت می‌گیرد. (ترفند مالش عبارت است از نوشتن $\delta (q,a)=\delta _{a}(q)$ به ازای همهٔ $q\in Q$). با این روش، تابع‌گذار به فرم ساده‌تری تبدیل می‌شود. ترکیب تابع تکرار شده یک مونوئید را تشکیل می‌دهد. برای توابع گذار، این مونوئید تحت نام مونوئید گذار یا در بعضی مواقع نیم‌گروه دگرسازی شناخته می‌شود.

با داشتن یک جفت از حروف $a,b\in \Sigma$ تابع جدید ${\widehat {\delta }}$ به صورت ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ تعریف می‌شود که $\circ$ نشان دهندهٔ ترکیب توابع است. طبیعتاً، این فرایند می‌تواند به‌طور بازگشتی ادامه یابد و بنابراین یک تعریف بازگشتی از تابع ${\widehat {\delta }}_{w}$ داریم که برای تمام کلمات $w\in \Sigma ^{*}$ تعریف شده است و به شرح زیر است:

${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

این ساختار می‌تواند معکوس هم بشود، با داشتن ${\widehat {\delta }}$، می‌توان دوباره $\delta$ را ساخت و بنابراین، این دو توصیف هم‌ارزند.

سه تایی $\langle Q,\Sigma ,\delta \rangle$ تحت نام ماشین نیمه خودکار شناخته می‌شود. ماشین نیمه خودکار همان ماشین خودکار است با این تفاوت که وضعیت شروع و مجموعهٔ وضعیت‌های قبول آن نادیده گرفته شده‌اند. مفهوم‌های افزودهٔ وضعیت اولیه و وضعیت قبول باعث می‌شوند تا توانائی ماشین خودکار بیش از توانائی ماشین نیمه خودکار باشد، بدین شرح که ماشین نیمه خودکار نمی‌تواند یک زبان صوری را شناسائی کند. زبان $L$ که توسط ماشین خودکار کران‌دار پذیرفته شده است، این گونه تعریف می‌شود:

$L=\{w\in \Sigma ^{\star }\,|\;{\widehat {\delta }}(q_{0},w)\in F\}$

زبان پذیرفته شدهٔ ماشین خودکار (یعنی $L$) مجموعه‌ای از کلمات $w$ است که با الفبای $\Sigma$ ساخته شده‌اند و وقتی به عنوان ورودی به ماشین خودکار داده می‌شوند، نهایتاً یکی از وضعیت‌های $F$ را نتیجه می‌دهند. زبان‌هایی را که توسط ماشین خودکار پذیرفته شده‌اند، زبان‌های قابل تشخیص می‌نامند.

وقتی مجموعهٔ وضعیت‌های Q کران‌دار است، ماشین خودکار به عنوان ماشین خودکار کران‌دار شناخته می‌شود و مجموعهٔ همهٔ زبان‌های قابل تشخیص آن را، زبان‌های باقاعده می‌نامیم. در واقع یک هم‌ارزی قوی وجود دارد: به ازای هر زبان باقاعده یک ماشین خودکار وضعیت محدود وجود دارد.

انواع ماشین‌های خودکار کران‌دار

این تصویر بیانگر نظریه ماشین‌ها می‌باشد

در زیر، سه نوع از ماشین‌های خودکار کران‌دار ذکر شده است.

ماشین‌های خودکار کران‌دار قطعی

هر وضعیت از یک ماشین خودکار از این نوع، یک‌گذار برای هر نشانه دارد.

ماشین‌های خودکار کران‌دار غیر قطعی

وضعیت‌های یک ماشین خودکار کراندار غیر قطعی، ممکن است برای هر نشانه یک‌گذار داشته باشد یا اصلاً انتقالی نداشته باشد یا حتی می‌تواند برای یک نشانه، گذارهای متعددی داشته باشد. این ماشین خودکار، کلمه را در صورتی می‌پذیرد که حداقل یک مسیر از $q_{0}$ به وضعیتی از $F$ وجود داشته باشد. اگرگذار تعریف نشده باشد، ماشین نمی‌داند که چگونه به خواندن ورودی ادامه دهد و در نتیجه کلمه پذیرفته نمی‌شود.

ماشین‌های خودکار کران‌دار غیر قطعی با ε-گذار

علاوه بر اینکه می‌توانند با هر نشانه‌ای به وضعیت‌های بیشتری (یا هیچ وضعیتی) پرش کنند، این ماشین‌ها می‌توانند که به روی هیچ نشانه‌ای پرش نکنند. به این معنا که، اگر یک وضعیت گذارهای نامگذاری شده با ε را دارد، این ماشین می‌تواند در هر وضعیتی که به وسیلهٔ ε-گذار به‌دست آمده قرار گیرد که این کار می‌تواند با واسطه یا بدون واسطهٔ وضعیت‌های دیگر صورت گیرد. مجموعهٔ وضعیت‌هایی که می‌توان به وسیلهٔ این شیوه از وضعیت $q$ به‌دست‌آورد، ε-بستار برای q نامیده می‌شود.

با این حال می‌توان نشان داد که تمام این ماشین‌ها، می‌توانند زبان‌های مشابهی را بپذیرند.

گسترهٔ ماشین‌های متناهی

خانوادهٔ زبان‌هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. هر چه یک ماشین قوی‌تر باشد، می‌تواند زبان‌های پیچیده‌تری را بپذیرد. ماشین‌های خودکاری که از این ماشین‌ها به‌شمار می‌آیند، عبارتند از:

ماشین‌های خودکار پشته‌ای

این ماشین‌ها همانند ماشین‌های خودکار کران‌دار قطعی (یا ماشین‌های خودکار کران‌دار غیر قطعی) هستند؛ با این تفاوت که حافظه را به صورت پشته به دوش می‌کشند؛ و بنابراین تابع‌گذار $\delta$ نیز به نشانه‌ای که در بالای پشته قرار دارد وابسته است و همین تابع مشخص می‌کند که در هر گذار، پشته چگونه باید تغییر داده شود. ماشین‌های پائین فشردنی غیر قطعی، زبان‌های مستقل از متن را می‌پذیرند.

ماشین‌های خودکار کراندار خطی

یک ماشین خودکار کران‌دار خطی، یک ماشین تورینگ غیرقطعی است که در آن، به جای یک نوار نامتناهی، فضایی متناسب با اندازهٔ رشتهٔ وارد شده، بر روی نوار وجود دارد. این ماشین‌ها زبان‌های حساس به متن را می‌پذیرند.

ماشین‌های تورینگ

این ماشین‌ها، قدرتمندترین ماشین‌های محاسباتی هستند. این ماشین‌ها دارای یک حافظهٔ نامتناهی (به شکل یک نوار) و یک هد (که می‌تواند نوار را بخواند و تغییر دهد و در سرتاسر نوار در هر جهتی جابه‌جا شود) هستند. ماشین‌های تورینگ با الگوریتم‌ها هم ارزند و پایهٔ نظری برای کامپیوترهای جدید می‌باشند. ماشین‌های تورینگ زبان‌های بازگشتی را می‌پذیرند و زبان‌های شمارش‌پذیر بازگشتی را شناسایی می‌کنند.

جایگشت اتوماتا

در نظریهٔ اتوماتا، جایگشت اتوماتا (به انگلیسی: Permutation automaton) یا ماشین گروه خالص (به انگلیسی: Pure-group machine) نوعی از ماشین تعیین‌پذیر حالات متناهی (DFA) است به طوری که هر نماد ورودی، جایگشتی از مجموعه‌ای از حالت‌ها باشد.

به عبارت دیگر، ماشین تعیین‌پذیر حالات متناهی (DFA) به نام A را می‌توان با چندتایی $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ نمایش داد که در آن Q مجموعهٔ وضعیت‌های ماشین، Σ مجموعهٔ نمادهای ورودی، δ تابع انتقال (که وضعیت q و نماد ورودی x را می‌گیرد و به وضعیت جدید $\delta (q,x)$ انتقال می‌دهد)، q_0 وضعیت شروع ماشین، و F مجموعهٔ وضعیت‌های پذیرفته‌شده (یا وضعیت پایانی) است.

ماشین A یک جایگشت اتوماتا است اگر و تنها اگر برای هر دو وضعیت مجزای q_i و q_j در Q و هر ورودی x در Σ داشته باشیم:

$\delta (q_{i},x)\neq \delta (q_{j},x)$

یک زبان صوری را p-منظم (p-regular) گویند اگر به وسیلهٔ یک ماشین جایگشت پذیرفته شود. به‌طور مثال، مجموعهٔ رشته‌های به طول زوج، یک زبان p-منظم به‌شمار می‌رود؛ این مجموعه می‌تواند به وسیلهٔ یک جایگشت اتوماتا با دو وضعیت که در هر انتقال، وضعیت فعلی با وضعیت دیگر جایگزین می‌شود، پذیرفته شود.

ویژگی‌های ریاضی

زبان‌های گروه خالص (pure-group) اولین خانوادهٔ جالب توجه از زبان‌های منظم بودند که حل مسئلهٔ ارتفاع ستاره (star height) برای آن‌ها به اثبات رسید تا محاسبه‌پذیر شوند.

مسئلهٔ ریاضی دیگری که در زبان‌های منظم مطرح می‌شود، مسئلهٔ «کلمات جداکننده» (separating words) نام دارد. این مسئله دربارهٔ اندازهٔ کوچک‌ترین ماشین تعیین‌پذیر حالات متناهی (DFA) است که بین دو کلمه به طول حداکثر n، از طریق پذیرفتن یکی و رد کردن دیگری، تمایز ایجاد می‌کند. کران بالای شناخته‌شده در حالت کلی برای این مسئله برابر با O(n^۲/۵ (log n)^۳/۵) است. این مسئله برای محدودیت جایگشت نیز بررسی شده است که در این حالت، کران بالای شناخته‌شده به O(n^۱/۲) تغییر می‌یابد.

جستارهای وابسته

• زبان‌های صوری
• اتوماتای سلولی
• ماشین‌های خودکار کران‌دار قطعی
• ماشین‌های تورینگ

منابع

• ریاضیات گسسته و کاربردهای آن (انگلیسی)

• Jackson, Jr. , Philip C. , Introduction to Artificial Intelligence, 2nd enlarged and slightly corrected ed. , Dover Publications, Inc. , New York, 1985. ISBN 0-486-24864-X
• An Introduction to Formal Languages and Automata, Peter Linz وب‌سایت کتاب