Turing Machine as Language Acceptor | ट्यूरिंग मशीन के रूप में भाषा स्वीकारक

Turing Machine (TM) एक computational model है जो यह निर्धारित करता है कि कोई string किसी भाषा का हिस्सा है या नहीं। जब Turing Machine किसी भाषा की सभी strings को स्वीकार करती है, तो कहा जाता है कि वह उस भाषा की acceptor machine है। इस अवधारणा को समझना महत्वपूर्ण है क्योंकि यह decidability और language recognition के सिद्धांत को परिभाषित करता है।

1️⃣ परिचय / Introduction

जैसे Finite Automata Regular Languages को स्वीकार करता है और PDA Context-Free Languages को, वैसे ही Turing Machine Recursively Enumerable Languages को स्वीकार करती है। यह किसी भी formal language को recognize करने का सबसे शक्तिशाली मॉडल है।

2️⃣ ट्यूरिंग मशीन का उद्देश्य / Purpose of a Turing Machine as Acceptor

एक Turing Machine को किसी भाषा के लिए acceptor के रूप में उपयोग करने का उद्देश्य यह है कि यह जांचा जा सके कि दी गई string उस भाषा की grammar द्वारा परिभाषित patterns का पालन करती है या नहीं।

Mathematically:

L(M) = { w | M accepts w }

जहाँ L(M) वह भाषा है जिसे Machine M स्वीकार करती है।

3️⃣ भाषा स्वीकार करने की प्रक्रिया / Language Acceptance Process

Turing Machine किसी string को स्वीकार करने के लिए निम्नलिखित चरणों का पालन करती है:

1. Input string tape पर लिखा जाता है।
2. Machine प्रारंभिक अवस्था (q₀) में शुरू होती है।
3. Transition Function δ के अनुसार symbols को पढ़ती और लिखती है।
4. यदि Machine accepting state (q_accept) पर पहुँच जाती है, तो string स्वीकार की जाती है।
5. यदि Machine rejecting state (q_reject) पर पहुँचती है, तो string अस्वीकार की जाती है।

4️⃣ ट्यूरिंग मशीन के दो प्रकार / Types of Turing Machines as Acceptors

• 1. Decider Turing Machine: यह हर input के लिए accept या reject state में रुकती है।
• 2. Recognizer (Semi-Decider) Turing Machine: यह केवल उन strings के लिए रुकती है जो भाषा में हैं, अन्यथा infinite loop में जा सकती है।

5️⃣ औपचारिक परिभाषा / Formal Definition of Acceptance

Turing Machine M किसी language L को accept करती है यदि:

∀ w ∈ Σ*, 
M accepts w ⇒ w ∈ L
M rejects or loops ⇒ w ∉ L

यहाँ “accept” का अर्थ है कि machine q_accept अवस्था तक पहुँचती है और रुक जाती है।

6️⃣ उदाहरण / Example

मान लें भाषा L = {aⁿbⁿ | n ≥ 1}

Objective: Equal number of a’s followed by b’s को स्वीकार करना।

Transition Function:

Working:

1. हर ‘a’ के लिए एक ‘b’ match किया जाता है।
2. सभी pairs match होने पर machine q_accept में जाती है।
3. यदि mismatch हो जाए → q_reject।

7️⃣ स्वीकार और अस्वीकार की स्थिति / Acceptance and Rejection Conditions

• Accept: जब machine q_accept अवस्था तक पहुँचती है और रुक जाती है।
• Reject: जब machine q_reject अवस्था तक पहुँचती है और रुक जाती है।
• Loop: जब machine कभी नहीं रुकती (non-halting condition)।

8️⃣ भाषा की पहचान / Recognizing a Language

Turing Machine उन सभी strings को पहचानती है जो उसकी स्वीकार्य भाषा (L) में आती हैं। यदि कोई string language के pattern से मेल नहीं खाती, तो machine उसे अस्वीकार कर देती है या infinite loop में चली जाती है।

9️⃣ Decidability और Recursively Enumerable Languages

• Decidable Language: जिसके लिए हर input पर TM halt होकर accept/reject करती है।
• Recursively Enumerable Language: जिसके लिए TM केवल accept करने वाले inputs पर halt करती है।

🔟 निष्कर्ष / Conclusion

Turing Machine as Acceptor computational theory का एक बुनियादी स्तंभ है। यह न केवल भाषाओं को पहचानने में मदद करती है, बल्कि यह भी निर्धारित करती है कि कौन-सी समस्याएँ algorithmically हल की जा सकती हैं। इस प्रकार, Turing Machine acceptance computation की सीमाओं और शक्ति दोनों को दर्शाता है।