Deterministic Finite Automata (DFA) | निश्चित सीमित ऑटोमाटा


Deterministic Finite Automata (DFA) | निश्चित सीमित ऑटोमाटा

Deterministic Finite Automata (DFA) या निश्चित सीमित ऑटोमाटा कंप्यूटर विज्ञान में सबसे मूलभूत गणनात्मक मॉडल है। यह मशीन किसी इनपुट स्ट्रिंग के आधार पर निश्चित नियमों का पालन करते हुए निर्णय लेती है कि स्ट्रिंग किसी विशेष भाषा (Language) का हिस्सा है या नहीं।

परिचय / Introduction

“Deterministic” का अर्थ है — हर स्थिति (State) और इनपुट प्रतीक (Input Symbol) के लिए केवल एक ही निश्चित ट्रांज़िशन (Transition) संभव है। DFA किसी इनपुट को पढ़ते हुए क्रमबद्ध (Sequential) रूप से आगे बढ़ती है और अंत में यह तय करती है कि इनपुट स्वीकार (Accepted) किया जाएगा या नहीं।

1️⃣ DFA की परिभाषा / Formal Definition

एक DFA को गणितीय रूप से 5-टपल (5-tuple) के रूप में परिभाषित किया जाता है:

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

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

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

जब कोई इनपुट स्ट्रिंग DFA में दी जाती है, तो यह स्ट्रिंग को एक-एक प्रतीक पढ़ते हुए विभिन्न अवस्थाओं में ट्रांज़िशन करती है। यदि संपूर्ण इनपुट पढ़ने के बाद मशीन Final State में होती है, तो इनपुट स्वीकार होता है; अन्यथा अस्वीकार।

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

यदि δ*(q₀, w) ∈ F, तब स्ट्रिंग w स्वीकार की जाती है।

3️⃣ DFA का उदाहरण / Example of DFA

एक DFA जो सभी स्ट्रिंग्स को पहचानता है जिनका अंत “01” से होता है:


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

Transition Function:
δ(q₀, 0) = q₁
δ(q₀, 1) = q₀
δ(q₁, 0) = q₁
δ(q₁, 1) = q₂
δ(q₂, 0) = q₁
δ(q₂, 1) = q₀

समझाइए:

यदि इनपुट स्ट्रिंग “1101” दी जाए, तो DFA q₂ अवस्था में समाप्त होगी, इसलिए स्ट्रिंग स्वीकार की जाएगी।

4️⃣ DFA का ट्रांज़िशन आरेख / Transition Diagram

  • हर state को एक वृत्त (circle) से दिखाया जाता है।
  • Arrow → Transition दर्शाता है।
  • Double circle → Final State।

5️⃣ DFA की विशेषताएँ / Features of DFA

  • हर state के लिए प्रत्येक इनपुट symbol पर केवल एक ही ट्रांज़िशन होता है।
  • मशीन memoryless होती है — यह केवल वर्तमान state पर निर्भर करती है।
  • यह Regular Languages को पहचानने के लिए उपयोग होती है।

6️⃣ DFA की सीमाएँ / Limitations

  • Nested या Context-Free patterns को पहचान नहीं सकती।
  • हर Regular Expression के लिए DFA बनाना जटिल हो सकता है।
  • NDFA की तुलना में इसका निर्माण अधिक समय ले सकता है।

7️⃣ NDFA और DFA के बीच तुलना / NDFA vs DFA Comparison

बिंदुDFANDFA
Transitionएक निश्चितएक से अधिक संभव
ComputationSequentialParallel
Epsilon Moveनहीं होताहो सकता है
Design Complexityनिश्चित और कठोरलचीला
Speedतेज़धीमा

8️⃣ DFA के अनुप्रयोग / Applications of DFA

  • Lexical Analysis in Compiler Design
  • Pattern Recognition Systems
  • Text Searching Algorithms (like regex engines)
  • Network Protocol Validation
  • Language Parsing

9️⃣ DFA के फायदे / Advantages

  • हर इनपुट के लिए स्पष्ट परिणाम देता है।
  • Hardware Implementation सरल है।
  • Mathematical Analysis में सटीक।

10️⃣ DFA की वास्तविक उपयोगिता / Real-World Use Case

Programming languages में compiler के lexical analyzer द्वारा keywords, identifiers, numbers आदि की पहचान DFA के माध्यम से की जाती है। उदाहरण: Regular Expression → Automata → Token Recognition।

निष्कर्ष / Conclusion

Deterministic Finite Automata (DFA) ऑटोमाटा सिद्धांत की सबसे मूलभूत और व्यावहारिक मशीन है। यह नियमित भाषाओं की पहचान का आधार है और कंपाइलर, प्रोटोकॉल तथा टेक्स्ट प्रोसेसिंग में महत्वपूर्ण भूमिका निभाती है।

Related Post