دستگاه دو طرفه قطعی متناهی

در علوم کامپیوتر، به طور خاص در نظریه اتوماتا، به ماشینی خودکار دو طرفه می‌گویند اگر اجازه دهد ورودی آن دوباره خوانده شود.

تعریف

دستگاه دو طرفه قطعی متناهی (به انگلیسی: two-way deterministic finite automaton) یا 2DFA یک ماشین انتزاعی است؛ نسخه‌ای تعمیم داده شده از دستگاه محدود قطعی (DFA) که می‌تواند دوباره کاراکترهای پردازش شده را ملاقات کند. همان‌طور که در DFA دیدیم، تعداد موقعیت‌ها متناهی است و هر انتقال با یک علامت مشخص شده که هر انتقال با علامت نشان داده شده مشخص می‌کند که دستگاه به سمت چپ حرکت می‌کند، راست، یا در همان موقعیت باقی می‌ماند. هم ارز، 2DFAها می‌تواند به عنوان تورینگ ماشین‌های فقط خواندنی بدون نوار کار، و با تنها یک نوار ورودی فقط خواندنی دیده شود.

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

تعریف رسمی

به طور رسمی، یک دستگاه دو طرفه قطعی متناهی را می‌توان توسط یک ۸ تایی زیر: $M=(Q,\Sigma ,L,R,\delta ,s,t,r)$ نشان داد به طوری که:

• $Q$ مجموعهٔ غیرتهی متناهی حالات
• $\Sigma$ مجموعهٔ غیرتهی متناهی الفبای ورودی
• $L$ علامت پایان سمت چپ است
• $R$ علامت پایان سمت راست است
• $\delta :Q\times (\Sigma \cup \{L,R\})ightarrowQ\times \{left,right\}$
• $s$ حالت شروع است
• $t$ حالت پایانی است
• $r$ حالت رد کردن

علاوه بر این، دو شرط زیر نیز باید ارضا شوند:

• برای همه $q\in Q$

$\delta (q,L)=(q^{\prime },right)$ برای برخی $q^{\prime }\in Q$

$\delta (q,R)=(q^{\prime },left)$ برای برخی $q^{\prime }\in Q$

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

• برای همهٔ نمادهای $\sigma \in \Sigma \cup \{L\}$

$\delta (t,\sigma )=(t,R)$

$\delta (r,\sigma )=(r,R)$

$\delta (t,R)=(t,L)$

$\delta (r,R)=(r,L)$

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

دستگاه دو طرفه متناهی کوانتومی

مفهوم 2DFAها توسط رابین و اسکات در سال ۱۹۵۹ در کار اصلی خود که "ماشین‌های متناهی و مشکلات تصمیم گیری" نام داشت مطرح شد که در سال ۱۹۹۷ توسط John Watrous به محاسبات کوانتومی تعمیم یاقته بود "On the Power of 2-Way Quantum Finite State Automata"، که او در آن نشان می‌دهد که این دستگاه می‌تواند زبان نامنظم تشخیص دهد و بسیار قوی تر از DFAها می‌باشد.

ماشین دو طرفه پشته‌ای

یک ماشین پشته‌ای است که اجازه حرکت در هر مسیری بر روی نوار ورودی خود را دارد که به آن دستگاه دو طرفه پشته‌ای (2PDA) می‌گویند که توسط Hartmanis، لوئیس، و استرنز در سال ۱۹۶۵ مورد مطالعه قرار گرفته است. Aho، Hopcroft، اولمن در سال ۱۹۶۸ و کوک در سال ۱۹۷۱ کلاس زبان‌های تشخیص دهنده 2DPDA (قطعی) و غیر قطعی (2NPDA) دستگاه دو طرفه پشته‌ای را را توصیف کرده‌اند. گری، هریسون، و ایبارا (۱۹۶۷) خصوصیات بستاری این زبان‌ها را بررسی نموده‌اند.

منابع

• Hing Leung. Two-Way Deterministic Finite Automata.
• M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3, 114–۱۲۵. ۱۹۵۹.