دستگاه دو طرفه قطعی متناهی
در علوم کامپیوتر، به طور خاص در نظریه اتوماتا، به ماشینی خودکار دو طرفه میگویند اگر اجازه دهد ورودی آن دوباره خوانده شود.
تعریف[ویرایش]
دستگاه دو طرفه قطعی متناهی (به انگلیسی: two-way deterministic finite automaton) یا 2DFA یک ماشین انتزاعی است؛ نسخهای تعمیم داده شده از دستگاه محدود قطعی (DFA) که میتواند دوباره کاراکترهای پردازش شده را ملاقات کند. همانطور که در DFA دیدیم، تعداد موقعیتها متناهی است و هر انتقال با یک علامت مشخص شده که هر انتقال با علامت نشان داده شده مشخص میکند که دستگاه به سمت چپ حرکت میکند، راست، یا در همان موقعیت باقی میماند. هم ارز، 2DFAها میتواند به عنوان تورینگ ماشینهای فقط خواندنی بدون نوار کار، و با تنها یک نوار ورودی فقط خواندنی دیده شود.
2DFAها میتوانند معادل با DFAها نشان داده شوند؛ که آن، هر زبان رسمی که بتواند توسط یک 2DFA پذیرفته شود میتواند توسط یک DFA که فقط به بررسی هر یک از کاراکترها به ترتیب میپردازد نیز پذیرفته شود. از آنجا که DFAها بدیهی است که یک مورد خاص از 2DFAها هستند، این به معنی این است که هر دو ماشین دقیقاً مجموعهای از زبانهای منظم را تشخیص میدهند. با این حال DFA معادل برای 2DFA ممکن است موقعیتهای بیشتری داشته باشند، و 2DFAها کارکرد عملی تری برای الگوریتمهایی با مشکلات شایع دارد. آنها همچنین معادل ماشین تورینگ فقط خواندنی هستند که تنها یک مقدار ثابت از فضا را بر روی نوار کار خود اشغال میکنند، زیرا هر مقدار ثابت از اطلاعات را میتوان در یک موقعیت کنترل متناهی توسط ساخت محصول گنجاند (یک موقعیت برای هر ترکیبی از یک موقعیت نوار کار و یک موقعیت کنترل).
تعریف رسمی[ویرایش]
به طور رسمی،[۱] یک دستگاه دو طرفه قطعی متناهی را میتوان توسط یک ۸ تایی زیر: نشان داد به طوری که:
- مجموعهٔ غیرتهی متناهی حالات
- مجموعهٔ غیرتهی متناهی الفبای ورودی
- علامت پایان سمت چپ است
- علامت پایان سمت راست است
- حالت شروع است
- حالت پایانی است
- حالت رد کردن
علاوه بر این، دو شرط زیر نیز باید ارضا شوند:
- برای همه
- برای برخی
- برای برخی
این گزارش میگوید که باید برخی از انتقال احتمالی وجود داشته باشد برای زمانی که اشاره گر الفبا به پایان میرسد.
- برای همهٔ نمادهای
این گزارش میگوید که یک بارکه دستگاه به موقعیت قبول یا رد میرسد، برای همیشه در آن باقی میماند و اشاره گر به سمت راستترین نماد رفته و به طور نامتناهی در آن میچرخد.
دستگاه دو طرفه متناهی کوانتومی[ویرایش]
مفهوم 2DFAها توسط رابین و اسکات در سال ۱۹۵۹ در کار اصلی خود که "ماشینهای متناهی و مشکلات تصمیم گیری" نام داشت مطرح شد که در سال ۱۹۹۷ توسط John Watrous به محاسبات کوانتومی تعمیم یاقته بود "On the Power of 2-Way Quantum Finite State Automata"، که او در آن نشان میدهد که این دستگاه میتواند زبان نامنظم تشخیص دهد و بسیار قوی تر از DFAها میباشد.[۲]
ماشین دو طرفه پشتهای[ویرایش]
یک ماشین پشتهای است که اجازه حرکت در هر مسیری بر روی نوار ورودی خود را دارد که به آن دستگاه دو طرفه پشتهای (2PDA)[۳] میگویند که توسط Hartmanis، لوئیس، و استرنز در سال ۱۹۶۵[۴] مورد مطالعه قرار گرفته است. Aho، Hopcroft، اولمن در سال ۱۹۶۸[۵] و کوک در سال ۱۹۷۱[۶] کلاس زبانهای تشخیص دهنده 2DPDA (قطعی) و غیر قطعی (2NPDA) دستگاه دو طرفه پشتهای را را توصیف کردهاند. گری، هریسون، و ایبارا (۱۹۶۷) خصوصیات بستاری این زبانها را بررسی نمودهاند.[۷]
منابع[ویرایش]
- ↑ This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University
- ↑ John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997. pdf
- ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: p.124; this paragraph is omitted in the 2003 edition.
- ↑ J. Hartmanis, P.M. {Lewis II}, R.E. Stearns (1965). "Hierarchies of Memory Limited Computations". Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design. pp. 179–190.
{{cite book}}
: نگهداری یادکرد:نامهای متعدد:فهرست نویسندگان (link) - ↑ Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman (1968). "Time and Tape Complexity of Pushdown Automaton Languages". Information and Control. 13 (3): 186–206. doi:10.1016/s0019-9958(68)91087-5.
{{cite journal}}
: نگهداری یادکرد:نامهای متعدد:فهرست نویسندگان (link) - ↑ S.A. Cook (1971). "Linear Time Simulation of Deterministic Two-Way Pushdown Automata". Proc. IFIP Congress. North Holland. pp. 75–80.
- ↑ Jim Gray, Michael A. Harrison, Oscar H. Ibarra (1967). "Two-Way Pushdown Automata". Information and Control. 11 (1–2): 30–70. doi:10.1016/s0019-9958(67)90369-5.
{{cite journal}}
: نگهداری یادکرد:نامهای متعدد:فهرست نویسندگان (link)
- 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–۱۲۵. ۱۹۵۹.