Two-Way Deterministic Finite Automata (2DFA) | द्विदिश निश्चित सीमित ऑटोमाटा

Two-Way Deterministic Finite Automata (2DFA) ऑटोमाटा सिद्धांत की एक उन्नत अवधारणा है जिसमें मशीन को इनपुट टेप (Input Tape) पर दोनों दिशाओं — बाएँ और दाएँ — में पढ़ने की अनुमति होती है। यह पारंपरिक DFA की तुलना में अधिक लचीलापन प्रदान करता है क्योंकि इसमें हेड (Head) केवल आगे ही नहीं बल्कि पीछे भी चल सकता है।

परिचय / Introduction

सामान्य DFA (One-Way DFA) इनपुट स्ट्रिंग को केवल एक दिशा में — बाएँ से दाएँ — पढ़ता है। जबकि 2DFA में मशीन किसी भी समय टेप पर आगे (Right Move → R) या पीछे (Left Move → L) जा सकती है। इससे भाषा पहचान (Language Recognition) की प्रक्रिया अधिक शक्तिशाली बनती है।

1️⃣ Two-Way DFA की परिभाषा / Definition of 2DFA

2DFA को औपचारिक रूप से निम्नलिखित 6-टपल (6-tuple) के रूप में परिभाषित किया जाता है:

M = (Q, Σ, δ, q₀, F, D)

Q – अवस्थाओं (States) का सीमित सेट
Σ – इनपुट वर्णमाला (Input Alphabet)
δ – ट्रांज़िशन फ़ंक्शन: Q × Σ → Q × {L, R}
q₀ – प्रारंभिक अवस्था (Start State)
F – अंतिम अवस्थाओं (Final States) का सेट
D – दिशा (Direction): L = Left, R = Right

ट्रांज़िशन फ़ंक्शन δ प्रत्येक state और input symbol के लिए अगली state तथा मूवमेंट दिशा (Left/Right) निर्धारित करता है।

2️⃣ 2DFA की कार्यप्रणाली / Working of 2DFA

मशीन टेप पर बाएँ से प्रारंभ होती है।
प्रत्येक इनपुट पढ़ने के बाद वह नई अवस्था में प्रवेश करती है और दिशा तय करती है।
यदि दिशा R है, तो हेड अगला प्रतीक पढ़ता है।
यदि दिशा L है, तो हेड पिछले प्रतीक पर लौट जाता है।
इनपुट समाप्त होने पर यदि मशीन Final State में है, तो स्ट्रिंग स्वीकार की जाती है।

नोट:

2DFA में हेड टेप के पहले प्रतीक से बाएँ नहीं जा सकता — ऐसा होने पर computation रुक जाता है।

3️⃣ उदाहरण / Example

एक Two-Way DFA जो भाषा L = {w | w का अंतिम प्रतीक ‘a’ है} को पहचानता है।

इनपुट स्ट्रिंग:

w = “abba”

ट्रांज़िशन फ़ंक्शन:

State	Input	Next State	Move
q₀	a	q₀	R
q₀	b	q₀	R
q₀	⊔ (end)	q₁	L
q₁	a	q₂ (Final)	S
q₁	b	Reject	S

यह मशीन अंत तक पहुँचने के बाद बाएँ लौटकर अंतिम प्रतीक की जाँच करती है। यदि वह ‘a’ है, तो स्ट्रिंग स्वीकार की जाती है।

4️⃣ 2DFA और 1DFA में अंतर / Difference Between 2DFA and 1DFA

विशेषता	1DFA	2DFA
Head Movement	केवल दाएँ	बाएँ और दाएँ दोनों
Memory	सीमित	अधिक नियंत्रण
Computation Power	समान Regular	Regular ही लेकिन अधिक लचीलापन
Implementation	सरल	जटिल
Determinism	पूर्णतया निश्चित	निश्चित लेकिन द्विदिश

मुख्य तथ्य:

यद्यपि 2DFA अधिक लचीला लगता है, लेकिन यह 1DFA के समान ही Regular Languages को पहचानता है। इसका अर्थ है कि 2DFA, 1DFA से अधिक computational power नहीं रखता — केवल processing का तरीका अलग है।

5️⃣ औपचारिक प्रमाण / Theoretical Proof (सारांश)

यह सिद्ध किया जा चुका है कि हर 2DFA के लिए एक equivalent 1DFA मौजूद है जो उसी भाषा को पहचानता है। Proof में 2DFA के head movements को finite control states में encode किया जाता है। इसलिए 2DFA और DFA computationally equivalent हैं।

6️⃣ 2DFA के लाभ / Advantages

समान इनपुट पर अधिक flexible control।
Backward checking संभव — जैसे स्ट्रिंग का अंतिम प्रतीक देखना।
String reversal जैसे tasks में उपयोगी।

7️⃣ सीमाएँ / Limitations

Implementation कठिन होता है क्योंकि हेड को नियंत्रित करना जटिल है।
Hardware में द्विदिश ट्रांज़िशन practically कठिन।
Computationally यह 1DFA से अधिक शक्तिशाली नहीं है।

8️⃣ 2DFA के उपयोग / Applications

Pattern Matching जहां स्ट्रिंग के दोनों छोरों की जाँच आवश्यक हो।
Lexical Scanning में Lookahead / Lookbehind operations के लिए।
Compiler Optimization Techniques में।

निष्कर्ष / Conclusion

Two-Way Deterministic Finite Automata (2DFA) एक सैद्धांतिक रूप से महत्वपूर्ण अवधारणा है जो finite automata को दोनों दिशाओं में कार्य करने की अनुमति देती है। हालाँकि यह computational power नहीं बढ़ाती, परंतु यह automata के structure और motion control की गहराई को समझने के लिए एक अनिवार्य model है।

Two-Way Deterministic Finite Automata (2DFA)

Two-Way DFA allows the read head to move both left and right on the input tape. It enhances DFA’s flexibility while maintaining the same computational capability — recognizing Regular Languages.

Formal Definition

M = (Q, Σ, δ, q₀, F, D)

δ: Q × Σ → Q × {L, R}
D = direction of movement (Left/Right)

Working

Reads input symbol.
Moves Left or Right based on δ.
Ends if head reaches tape boundary or final state.

Example

Language L = {w | last symbol is ‘a’}


q₀ -a→ q₀ (R)
q₀ -b→ q₀ (R)
q₀ -⊔→ q₁ (L)
q₁ -a→ q₂ (Accept)

Comparison Table

Feature	DFA	2DFA
Direction	Right only	Left and Right
Memory	Limited	More flexible control
Computation Power	Regular	Regular
Ease of Implementation	Simple	Complex

Proof of Equivalence

Every 2DFA can be simulated by a 1DFA. Thus, 2DFA does not recognize any language beyond regular languages.

Applications

Lookahead and Lookbehind in lexical analysis.
Bidirectional pattern recognition.
Advanced string parsing and validation.

Conclusion

Two-Way DFA offers theoretical depth in understanding automata head movement and control. Though it doesn’t increase computational power, it enhances conceptual understanding of automata mechanics.

Church’s Thesis and Complexity Theory (P vs NP) | चर्च का सिद्धांत और जटिलता सिद्धांत (P बनाम NP समस्याएँ)

Church’s Thesis and Complexity Theory (P vs NP) | चर्च का सिद्...

Solvability and Unsolvability Concepts | हल करने योग्य और अ-हल करने योग्य समस्याएँ

Solvability and Unsolvability Concepts | हल करने योग्य और ...

Halting Problem and Post Correspondence Problem | हॉल्टिंग समस्या और पोस्ट पत्राचार समस्या

Halting Problem and Post Correspondence Problem | हॉल्टिंग समस...

Unrestricted Grammars and Type-0 Languages | असीमित व्याकरण और टाइप-0 भाषाएँ

Unrestricted Grammars and Type-0 Languages | असीमित व्याकर�...

Recursive and Recursively Enumerable Languages | पुनरावर्ती और पुनरावर्ती रूप से गणनीय भाषाएँ

Recursive and Recursively Enumerable Languages | पुनरावर्ती औ�...

Two-Way Deterministic Finite Automata (2DFA) | द्विदिश निश्चित सीमित ऑटोमाटा