Finite Automata as Language Acceptor and Translator | भाषा स्वीकारक और अनुवादक के रूप में सीमित ऑटोमाटा

Finite Automata (FA) ऑटोमाटा सिद्धांत की सबसे मूलभूत मशीन है, जो किसी भाषा को पहचानने (Acceptance) या अनुवाद करने (Translation) का कार्य करती है। यह सीमित अवस्थाओं (Finite States) के माध्यम से इनपुट स्ट्रिंग को पढ़कर यह तय करती है कि स्ट्रिंग भाषा का हिस्सा है या नहीं। इसके अलावा, इसे ट्रांसलेटर के रूप में भी उपयोग किया जा सकता है जो एक इनपुट को दूसरे आउटपुट में परिवर्तित करता है।

परिचय / Introduction

Finite Automata एक औपचारिक गणितीय मॉडल है जिसका उपयोग Regular Languages को पहचानने के लिए किया जाता है। यह एक ‘Language Acceptor’ के रूप में कार्य करता है जो केवल उन स्ट्रिंग्स को स्वीकार करता है जो निर्दिष्ट नियमों के अनुरूप होती हैं। वहीं, Translator के रूप में यह स्ट्रिंग को एक नए रूप में परिवर्तित कर सकता है।

1️⃣ Finite Automata का औपचारिक निरूपण / Formal Definition

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

M = (Q, Σ, δ, q₀, F), जहाँ:

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

2️⃣ Language Acceptor के रूप में Finite Automata

Finite Automata किसी भाषा की स्ट्रिंग्स को स्वीकार या अस्वीकार करने के लिए उपयोग किया जाता है। यदि कोई स्ट्रिंग मशीन को प्रारंभिक अवस्था से किसी स्वीकृति अवस्था तक ले जाती है, तो वह स्ट्रिंग उस भाषा का हिस्सा मानी जाती है।

उदाहरण / Example

मान लीजिए भाषा L = {w | w का अंत 1 से होता है}, Σ = {0,1}

Q = {q₀, q₁}
Σ = {0, 1}
q₀ प्रारंभिक अवस्था है
F = {q₁}
Transition Function:
δ(q₀, 0) = q₀
δ(q₀, 1) = q₁
δ(q₁, 0) = q₀
δ(q₁, 1) = q₁

इस FA द्वारा वे सभी स्ट्रिंग्स स्वीकार की जाती हैं जिनका अंतिम प्रतीक 1 है, जैसे 01, 101, 111।

3️⃣ Transition Diagram (ट्रांज़िशन आरेख)

FA को ग्राफ के रूप में भी दर्शाया जा सकता है जहाँ वृत्त (nodes) अवस्थाएँ दर्शाते हैं और तीर (edges) ट्रांज़िशन।

• Double Circle → Final State
• Arrow → Transition based on input symbol

4️⃣ Language Recognition / भाषा पहचान

Finite Automata की शक्ति इस बात में निहित है कि यह केवल Regular Languages को ही पहचान सकता है। यह Context-Free या अधिक जटिल भाषाओं को नहीं पहचान सकता।

भाषा पहचान प्रक्रिया / Process of Acceptance

1. मशीन q₀ से शुरू होती है।
2. हर इनपुट प्रतीक के लिए δ ट्रांज़िशन लागू होता है।
3. यदि पूरी स्ट्रिंग पढ़ने के बाद मशीन Final State F में है → स्ट्रिंग स्वीकार ✅
4. अन्यथा → अस्वीकार ❌

5️⃣ Finite Automata as Translator / अनुवादक के रूप में सीमित ऑटोमाटा

FA को Output Function जोड़कर एक Translator के रूप में प्रयोग किया जा सकता है। जब हम प्रत्येक इनपुट पर एक आउटपुट उत्पन्न करते हैं, तो हमें दो प्रकार की मशीनें मिलती हैं — Moore Machine और Mealy Machine।

Moore Machine

• Output केवल State पर निर्भर करता है।
• Formal Definition: M = (Q, Σ, Δ, δ, λ, q₀)
• यह प्रत्येक स्थिति के लिए आउटपुट निर्धारित करता है।

Mealy Machine

• Output इनपुट और स्थिति दोनों पर निर्भर करता है।
• यह ट्रांज़िशन के समय आउटपुट उत्पन्न करती है।

उदाहरण / Example

एक Mealy Machine जो इनपुट बिट्स के लिए ‘1’ की गिनती करती है और हर इनपुट के बाद आउटपुट के रूप में कुल गिनती देती है।

6️⃣ Finite Automata in Real-World Applications

• Compiler Design: Lexical Analysis (Token Recognition)
• Digital Circuits: Sequential Logic Design
• Search Algorithms: Regular Expression Matching
• Protocol Verification

7️⃣ Limitation of Finite Automata

• Memoryless: यह केवल वर्तमान स्थिति को याद रखता है।
• Nested Patterns को नहीं पहचान सकता।
• Non-Regular Languages को पहचानने में असमर्थ।

निष्कर्ष / Conclusion

Finite Automata किसी भाषा को पहचानने और अनुवाद करने की सबसे बुनियादी मशीन है। इसकी संरचना सरल होने के बावजूद यह आधुनिक कंप्यूटर विज्ञान के कई क्षेत्रों जैसे Compiler Design, Network Protocols और Text Processing में महत्वपूर्ण भूमिका निभाती है। DFA और NFA इसके दो सबसे महत्वपूर्ण रूप हैं जो भाषा पहचान की नींव रखते हैं।