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

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

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

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

== تعریف رسمی ==
به طور رسمی،<ref>This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University</ref> یک دستگاه دو طرفه قطعی متناهی را می‌توان توسط یک ۸ تایی زیر:
<math>M=(Q,\Sigma,L,R,\delta,s,t,r)</math>
نشان داد به طوری که:
* <math>Q</math> مجموعهٔ غیرتهی متناهی حالات
* <math>\Sigma</math> مجموعهٔ غیرتهی متناهی الفبای ورودی
* <math>L</math> علامت پایان سمت چپ است
* <math>R</math> علامت پایان سمت راست است
* <math>\delta: Q \times (\Sigma \cup \{L,R\}) ightarrow Q \times \{left,right\}</math>
* <math>s</math> حالت شروع است
* <math>t</math> حالت پایانی است
* <math>r</math> حالت رد کردن

علاوه بر این، دو شرط زیر نیز باید ارضا شوند:
* برای همه <math>q \in Q</math>

:<math>\delta(q,L)=(q^\prime,right)</math> برای برخی <math>q^\prime \in Q</math>

:<math>\delta(q,R)=(q^\prime,left)</math> برای برخی <math>q^\prime \in Q</math>

این گزارش می‌گوید که باید برخی از انتقال احتمالی وجود داشته باشد برای زمانی که اشاره گر الفبا به پایان می‌رسد.
* برای همهٔ نمادهای <math>\sigma \in \Sigma \cup \{L\}</math>

: <math>\delta(t,\sigma)=(t,R)</math>
: <math>\delta(r,\sigma)=(r,R)</math>
: <math>\delta(t,R)=(t,L)</math>
: <math>\delta(r,R)=(r,L)</math>

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

== دستگاه دو طرفه متناهی کوانتومی ==
مفهوم 2DFAها توسط رابین و اسکات در سال ۱۹۵۹ در کار اصلی خود که "ماشین‌های متناهی و مشکلات [[تصمیم‌گیری|تصمیم گیری]]" نام داشت مطرح شد که در سال ۱۹۹۷ توسط [[John Watrous]] به محاسبات کوانتومی تعمیم یاقته بود "On the Power of 2-Way Quantum Finite State Automata"، که او در آن نشان می‌دهد که این دستگاه می‌تواند زبان نامنظم تشخیص دهد و بسیار قوی تر از DFAها می‌باشد.<ref>[[John Watrous (computer scientist)|John Watrous]]. [http://citeseer.ist.psu.edu/article/watrous97power.html On the Power of 2-Way Quantum Finite State Automata]. CS-TR-1997-1350. 1997. [ftp://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]</ref>

== ماشین دو طرفه پشته‌ای ==
یک [[ماشین پشته‌ای]] است که اجازه حرکت در هر مسیری بر روی نوار ورودی خود را دارد که به آن '''دستگاه دو طرفه پشته‌ای''' (2PDA)<ref>{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| url=https://archive.org/details/trent_0116301269779| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X}} Here: p.124; this paragraph is omitted in the 2003 edition.</ref> می‌گویند که توسط Hartmanis، لوئیس، و استرنز در سال ۱۹۶۵<ref>{{cite book| author=J. Hartmanis, P.M. {Lewis II}, R.E. Stearns| chapter=Hierarchies of Memory Limited Computations| title=Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design| year=1965| pages=179–190}}</ref> مورد مطالعه قرار گرفته است. Aho، Hopcroft، اولمن در سال ۱۹۶۸<ref>{{cite journal| author=Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman| title=Time and Tape Complexity of Pushdown Automaton Languages| journal=Information and Control| year=1968| volume=13| number=3| pages=186-206| doi=10.1016/s0019-9958(68)91087-5}}</ref> و کوک در سال ۱۹۷۱<ref>{{cite book| author=S.A. Cook| chapter=Linear Time Simulation of Deterministic Two-Way Pushdown Automata| title=Proc. IFIP Congress| year=1971| pages=75-80| publisher=North Holland}}</ref> کلاس زبان‌های تشخیص دهنده 2DPDA (قطعی) و غیر قطعی (2NPDA) دستگاه دو طرفه پشته‌ای را را توصیف کرده‌اند. گری، هریسون، و ایبارا (۱۹۶۷) خصوصیات بستاری این زبان‌ها را بررسی نموده‌اند.<ref>{{cite journal| author=Jim Gray, Michael A. Harrison, Oscar H. Ibarra| title=Two-Way Pushdown Automata| journal=Information and Control| year=1967| volume=11| number=1–2| pages=30–70| doi=10.1016/s0019-9958(67)90369-5}}</ref>

== منابع ==
{{پانویس|۲|چپ‌چین=بله}}
{{چپ‌چین}}
* Hing Leung. [http://www.math.nmsu.edu/hist_projects/2DFA.pdf 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&ndash;۱۲۵. ۱۹۵۹.
{{پایان چپ‌چین}}

[[رده:ماشین متناهی]]
[[رده:نظریه اتوماتا]]