Non-Deterministic Finite Automata (NDFA) | अनिश्चित सीमित ऑटोमाटा

Non-Deterministic Finite Automata (NDFA) या NFA ऑटोमाटा सिद्धांत की एक मौलिक अवधारणा है। यह Finite Automata का ऐसा रूप है जिसमें किसी विशेष अवस्था (state) और इनपुट प्रतीक (input symbol) के लिए एक से अधिक संभावित ट्रांज़िशन (transitions) हो सकते हैं। इस प्रकार की मशीन यह दर्शाती है कि किसी भी स्थिति पर मशीन के पास कई संभावनाएँ हो सकती हैं।

परिचय / Introduction

Automata Theory में Non-Determinism का अर्थ है कि किसी इनपुट पर मशीन एक से अधिक दिशा में जा सकती है। जबकि Deterministic Automata में हर इनपुट के लिए केवल एक निश्चित अगली अवस्था होती है, NFA में यह निश्चित नहीं होता कि मशीन किस अवस्था में जाएगी।

1️⃣ NDFA की परिभाषा / Definition of NDFA

एक NDFA को औपचारिक रूप से एक 5-टपल (5-tuple) के रूप में परिभाषित किया जाता है:

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

• Q = अवस्थाओं (States) का सीमित सेट
• Σ = इनपुट वर्णमाला (Input Alphabet)
• δ = ट्रांज़िशन फ़ंक्शन (Q × Σ → P(Q)) — यह Power Set देता है
• q₀ = प्रारंभिक अवस्था (Start State)
• F = स्वीकृति अवस्थाओं (Final States) का सेट

मुख्य अंतर / Key Difference:

Deterministic FA में δ हर इनपुट पर एक state देता है जबकि NFA में δ एक से अधिक states दे सकता है।

2️⃣ NDFA में ε-ट्रांज़िशन / ε-Transitions in NDFA

NDFA में ε (epsilon) ट्रांज़िशन भी हो सकते हैं। इसका अर्थ है कि मशीन किसी इनपुट प्रतीक के बिना भी एक अवस्था से दूसरी अवस्था में जा सकती है।

उदाहरण:

यदि δ(q₁, ε) = {q₂, q₃}, तो मशीन q₁ से q₂ या q₃ पर बिना किसी इनपुट के जा सकती है।

3️⃣ NDFA का कार्य सिद्धांत / Working of NDFA

जब कोई स्ट्रिंग इनपुट की जाती है, NDFA कई संभावित मार्गों (paths) पर समानांतर कार्य करता है। यदि किसी एक मार्ग पर मशीन Final State तक पहुँच जाती है, तो इनपुट स्ट्रिंग स्वीकार की जाती है।

भाषा स्वीकार्यता की शर्त:

यदि किसी एक ट्रांज़िशन श्रृंखला में मशीन किसी Final State F ∈ Q तक पहुँचती है, तो स्ट्रिंग भाषा का हिस्सा मानी जाती है।

4️⃣ उदाहरण / Example

एक NDFA जो उन सभी स्ट्रिंग्स को स्वीकार करता है जिनका अंत ‘1’ से होता है:

Q = {q₀, q₁}
Σ = {0, 1}
q₀ = प्रारंभिक अवस्था
F = {q₁}

δ(q₀, 0) = {q₀}
δ(q₀, 1) = {q₀, q₁}
δ(q₁, 0) = {q₁}
δ(q₁, 1) = {q₁}

समझाइए:

इनपुट ‘101’ के लिए मशीन दो paths पर जा सकती है। यदि किसी path पर Final State q₁ प्राप्त होती है तो स्ट्रिंग स्वीकार कर ली जाती है।

5️⃣ NDFA का ग्राफिकल निरूपण / Graphical Representation

• States को वृत्त (circles) से दिखाया जाता है।
• Transitions को directed arrows द्वारा प्रदर्शित किया जाता है।
• ε ट्रांज़िशन dotted arrow द्वारा दर्शाए जाते हैं।

6️⃣ NDFA और DFA में अंतर / Difference Between NDFA and DFA

बिंदु	NDFA	DFA
Transition	एक से अधिक संभव	केवल एक निश्चित
Epsilon Move	संभव	संभव नहीं
Computation	Parallel	Sequential
Complexity	सरल डिज़ाइन	कठोर डिज़ाइन

7️⃣ NDFA के फायदे / Advantages

• डिज़ाइन करना आसान होता है।
• एक ही भाषा के लिए छोटे आकार की मशीन संभव है।
• ε ट्रांज़िशन से लचीलापन बढ़ता है।

8️⃣ NDFA की सीमाएँ / Limitations

• Implementation में कठिनाई क्योंकि मशीन को कई paths संभालने होते हैं।
• Hardware या Software में direct execution कठिन है।

9️⃣ NDFA से DFA में रूपांतरण / Conversion (Overview)

हर NDFA के लिए एक equivalent DFA मौजूद होता है। यह रूपांतरण Subset Construction Method द्वारा किया जाता है, जिसमें NDFA के सभी संभावित state sets को DFA की states माना जाता है। (इस पर अगले ब्लॉग में विस्तार से चर्चा होगी)

निष्कर्ष / Conclusion

Non-Deterministic Finite Automata (NDFA) भाषा पहचान (Language Recognition) के लिए एक शक्तिशाली सैद्धांतिक उपकरण है। यद्यपि इसका प्रत्यक्ष कार्यान्वयन कठिन है, लेकिन यह DFA के निर्माण और Regular Language Theory की नींव रखता है।