Context-Sensitive Grammar (CSG) in Automata | ऑटोमाटा में प्रसंग-संवेदनशील व्याकरण

Context-Sensitive Grammar (CSG) औपचारिक भाषा सिद्धांत (Formal Language Theory) की एक महत्वपूर्ण व्याकरणिक श्रेणी है, जो Context-Sensitive Languages (CSLs) को परिभाषित करती है। यह Type-1 Grammar कहलाती है और Regular तथा Context-Free Grammar से अधिक शक्तिशाली होती है। इसका उपयोग उन भाषाओं को परिभाषित करने के लिए किया जाता है जहाँ किसी प्रतीक (Symbol) का उत्पादन उसके संदर्भ (Context) पर निर्भर करता है।

परिचय / Introduction

Context-Sensitive Grammar वह grammar है जिसमें production rules ऐसे होते हैं कि Left-hand side की लंबाई हमेशा Right-hand side की लंबाई से कम या बराबर होती है। यहाँ production rule का उपयोग context पर आधारित होता है, यानी symbol को केवल तभी बदला जा सकता है जब वह एक निश्चित परिवेश (Surrounding Symbols) में हो।

1️⃣ औपचारिक परिभाषा / Formal Definition

एक Context-Sensitive Grammar को औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:

G = (V, T, P, S)

• V → Non-terminals का सेट
• T → Terminals का सेट
• P → Productions का सेट जहाँ प्रत्येक production αAβ → αγβ के रूप में है, जहाँ α, β ∈ (V ∪ T)* और γ ∈ (V ∪ T)+
• S → Start Symbol

और प्रत्येक production rule के लिए यह शर्त होनी चाहिए:

|αAβ| ≤ |αγβ| (अर्थात्, production rule non-contracting होना चाहिए)

2️⃣ उदाहरण / Example

एक CSG जो भाषा L = {aⁿbⁿcⁿ | n ≥ 1} को generate करती है:

S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

Derivation of “aabbcc”:

S ⇒ aSBC
  ⇒ aaSBCBC
  ⇒ aaabcBC
  ⇒ aabbcC
  ⇒ aabbcc

निष्कर्ष:

यह Grammar केवल उसी स्थिति में सही ढंग से स्ट्रिंग्स बनाती है जहाँ a, b, और c की संख्या समान हो।

3️⃣ Context का अर्थ / Meaning of Context

Context-sensitive का अर्थ है कि किसी Non-terminal का Replacement उसके आस-पास के प्रतीकों पर निर्भर करता है। उदाहरण के लिए, αAβ → αγβ में, A का production α और β (इसके context) पर निर्भर करता है।

4️⃣ Context-Sensitive Grammar के गुण / Properties of CSG

• Non-contracting grammar होती है (अर्थात्, Output छोटा नहीं हो सकता)।
• यह Linear Bounded Automata (LBA) द्वारा पहचानी जाती है।
• Regular और Context-Free Grammars इसका subset हैं।
• यह Type-1 Grammar कहलाती है (Chomsky Hierarchy के अनुसार)।

5️⃣ Linear Bounded Automata (LBA) से संबंध

Context-Sensitive Languages को Linear Bounded Automata (LBA) नामक मशीनें पहचान सकती हैं। LBA एक प्रकार का Restricted Turing Machine है, जिसकी tape लंबाई इनपुट के आकार तक सीमित होती है।

Relation:

• हर Context-Sensitive Grammar के लिए एक Equivalent LBA मौजूद होता है।
• हर LBA एक Context-Sensitive Language को पहचान सकता है।

6️⃣ Context-Sensitive Grammar बनाम Context-Free Grammar

7️⃣ Context-Sensitive Grammar के उदाहरण

• L₁ = {aⁿbⁿcⁿ | n ≥ 1}
• L₂ = {aⁿbⁿcᵐdᵐ | n,m ≥ 1}
• L₃ = {w w | w ∈ {a,b}*}

8️⃣ Context-Sensitive Grammar के उपयोग / Applications

• Natural Language Processing (NLP) में Syntax Understanding के लिए।
• Compiler Design में Semantic Checking के लिए।
• Complex Programming Languages के Grammar Parsing में।
• Mathematical Linguistics और AI में।

9️⃣ लाभ / Advantages

• CFG से अधिक शक्तिशाली व्याकरण।
• Multiple dependency वाले भाषाई patterns को handle कर सकता है।
• Ambiguity को कम करता है।

🔟 सीमाएँ / Limitations

• Design और Parsing कठिन।
• Computation समय अधिक लगता है।
• प्रायः केवल Theoretical अध्ययन के लिए प्रयोग किया जाता है।

निष्कर्ष / Conclusion

Context-Sensitive Grammar औपचारिक भाषा सिद्धांत की सबसे शक्तिशाली व्याकरणों में से एक है। यह उन भाषाओं को परिभाषित करती है जिन्हें Regular या Context-Free Grammar व्यक्त नहीं कर सकती। LBA मशीनें इन्हें पहचानने में सक्षम होती हैं, और यह भाषा सिद्धांत की उच्च स्तरीय समझ के लिए आवश्यक है।