Two-way Deterministic Finite Automaton (2DFA) in Hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation

Unit 2

Types of Finite Automata

Topic 10 : Two-way Deterministic Finite Automaton (2DFA) in Hindi

एक Two-way Deterministic Finite Automaton (2DFA) एक abstract machine है, जो Deterministic Finite Automaton (DFA) का एक generalized version है जो पहले से processed charactersको re-send कर सकता है। DFA की तरह, current character के आधार पर उन दोनों के बीच transitions के साथ States की एक सीमित संख्या होती है, लेकिन प्रत्येक transitions को एक value के साथ भी labelled किया जाता है, यह दर्शाता है कि machine input में अपनी स्थिति को left , right या stay या नहीं उसी स्थिति में। समान रूप से, 2DFA को केवल work tape के साथ read-only Turing machines के रूप में देखा जा सकता है।

2 DFA को Rabin and Scott द्वारा 1958 के पेश किया गया था, जिन्होंने उन्हें one-way DFAs के बराबर शक्ति प्रदान की। किसी भी formal language को जिसे एक 2DFA द्वारा मान्यता प्राप्त किया जा सकता है, एक DFA द्वारा पहचाना जा सकता है जो केवल order में each character की जांच और खपत करता है। चूंकि DFA Clearly 2 DFA का एक special case है, इसका मतलब है कि दोनों प्रकार की machines regularly regular language के group को पहचानती हैं। हालाँकि, 2DFA के लिए बराबर DFA को कई states की आवश्यकता हो सकती है, जिससे 2DFA कुछ सामान्य समस्याओं के लिए algorithm के लिए अधिक Practical representation करता है।

2DFA केवल read-only Turing machines के equivalent है जो अपने work tape पर केवल एक constant amount का उपयोग करती हैं, क्योंकि किसी भी information को product construction के माध्यम से finite control state में शामिल किया जा सकता है (प्रत्येक work tape के लिए एक state और control state होता है )।