Linear Bounded Automata and Context Sensitive Languages | रैखिक सीमाबद्ध ऑटोमाटा और प्रसंग-संवेदनशील भाषाएँ

Linear Bounded Automata (LBA) और Context-Sensitive Languages (CSL) computation theory में Turing Machine के विशेष रूप हैं, जो सीमित स्मृति (limited memory) के साथ भाषा पहचान (language recognition) का कार्य करते हैं। LBA को एक विशेष प्रकार की Non-deterministic Turing Machine (NTM) माना जाता है जो input size के अनुसार linear tape पर काम करती है। Context-Sensitive Languages वही भाषाएँ हैं जिन्हें LBA पहचान सकती है।

1️⃣ परिचय / Introduction

Context-Sensitive Languages (CSLs) वे भाषाएँ हैं जो Context-Sensitive Grammar (CSG) द्वारा generate की जाती हैं। Linear Bounded Automata इन्हीं भाषाओं को recognize करने का कार्य करता है। LBA, Turing Machine का restricted version है जिसमें tape की लंबाई input length के कुछ linear multiple तक सीमित होती है।

अर्थात, यदि input की लंबाई n है, तो tape length ≤ k·n (जहाँ k एक स्थिरांक है)। इसलिए LBA finite memory और powerful computation का संतुलित रूप है।

2️⃣ Linear Bounded Automata (LBA) की परिभाषा / Definition of LBA

LBA को formally एक tuple के रूप में परिभाषित किया जाता है:

M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

• Q → finite set of states
• Σ → input alphabet
• Γ → tape alphabet (Σ ⊆ Γ)
• δ → transition function: Q × Γ → Q × Γ × {L, R}
• q₀ → initial state
• q_accept → accepting state
• q_reject → rejecting state

Difference from Turing Machine → LBA input tape को input length से अधिक extend नहीं कर सकती। इसका अर्थ है कि computation केवल उस क्षेत्र तक सीमित रहेगा जहाँ input symbols मौजूद हैं।

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

1. LBA input string को tape पर पढ़ती है।
2. यह केवल उसी क्षेत्र में head को move कर सकती है जहाँ input symbols मौजूद हैं।
3. Transition function symbols को बदलती है और head को L या R direction में move करती है।
4. यदि machine accept state में पहुँच जाती है, तो string स्वीकार की जाती है।

LBA की computational शक्ति Context-Sensitive Grammar के बराबर होती है।

4️⃣ Context-Sensitive Grammar (CSG) की परिभाषा / Definition of CSG

Context-Sensitive Grammar एक formal grammar है जिसमें प्रत्येक production rule निम्नलिखित रूप में होती है:

αAβ → αγβ

• α, β ∈ (V ∪ T)*
• A → Non-terminal
• γ ∈ (V ∪ T)+ (i.e., γ ≠ ε)

इसका अर्थ है कि grammar में किसी variable को उसके आसपास के context के आधार पर बदला जा सकता है। इसलिए इसे Context-Sensitive कहा जाता है।

उदाहरण:

Grammar G:
S → aSBC | abc
CB → BC
bB → bb
cC → cc

यह grammar language L = {aⁿbⁿcⁿ | n ≥ 1} generate करती है।

5️⃣ LBA द्वारा भाषा पहचान / Language Recognition by LBA

LBA Context-Sensitive Language को पहचानने के लिए design किया जाता है। इसका operation निम्नलिखित तरीके से होता है:

1. Input tape पर string w लिखी जाती है।
2. LBA symbols को read और rewrite करती है, लेकिन tape की सीमा cross नहीं करती।
3. यदि grammar rules के अनुसार string valid है, तो machine accept करती है।
4. अन्यथा, machine reject या halt कर जाती है।

6️⃣ LBA का उदाहरण / Example of LBA

Language: L = {aⁿbⁿcⁿ | n ≥ 1}

Objective: Equal number of a’s, b’s, and c’s को पहचानना।

Working:

• पहले symbol ‘a’ को X से replace करें।
• फिर दाएँ जाकर पहला ‘b’ ढूँढें → उसे Y से replace करें।
• फिर दाएँ जाकर पहला ‘c’ ढूँढें → उसे Z से replace करें।
• फिर बाएँ लौटकर अगला ‘a’ खोजें।
• यदि सभी symbols X, Y, Z से बदल दिए गए हों → accept।

Acceptance:

यदि सभी a, b, c का count समान है → string accept होगी, अन्यथा machine reject करेगी।

7️⃣ Context-Sensitive Language की विशेषताएँ / Properties of CSL

• CSL ⊃ Context-Free Languages
• CSL को हमेशा LBA द्वारा recognize किया जा सकता है।
• CSL में ε (empty string) नहीं होती।
• CSL deterministic या non-deterministic दोनों प्रकार की हो सकती हैं।

8️⃣ CSL vs CFL / Comparison Table

9️⃣ Context-Sensitive Languages के उपयोग / Applications

• Natural Language Processing (NLP)
• Compiler Design (Syntax Checking)
• Complex Pattern Recognition
• Bioinformatics (DNA pattern modeling)
• Machine Translation Systems

🔟 निष्कर्ष / Conclusion

Linear Bounded Automata एक महत्वपूर्ण computation model है जो Context-Sensitive Languages को recognize करता है। यह Turing Machine से सीमित लेकिन PDA से अधिक शक्तिशाली है। इस प्रकार, LBA और CSL के बीच का संबंध computation hierarchy में एक अनिवार्य कड़ी है, जो दिखाता है कि सीमित संसाधनों के साथ भी जटिल भाषाओं को पहचाना जा सकता है।