Context-Free Grammar (CFG) in Automata | ऑटोमाटा में प्रसंग-मुक्त व्याकरण

Context-Free Grammar (CFG) औपचारिक भाषा सिद्धांत (Formal Language Theory) में एक महत्वपूर्ण व्याकरणिक मॉडल है जो Context-Free Languages (CFL) को परिभाषित करता है। CFG का प्रयोग प्रोग्रामिंग भाषाओं, कंपाइलर डिज़ाइन और भाषा पार्सिंग (Parsing) में व्यापक रूप से किया जाता है।

परिचय / Introduction

Context-Free Grammar वह व्याकरण है जिसमें हर production rule के बाएँ (Left-hand side) में केवल एक Non-terminal symbol होता है, और दाएँ (Right-hand side) में Terminals और Non-terminals का कोई भी क्रम (Sequence) हो सकता है। इसे “Context-Free” इसलिए कहा जाता है क्योंकि इसका उत्पादन (Production) नियम उस प्रतीक (Symbol) के context पर निर्भर नहीं करता।

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

एक Context-Free Grammar को इस प्रकार दर्शाया जा सकता है:

G = (V, T, P, S)

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

उदाहरण:

Grammar G = (V, T, P, S)

V = {S}
T = {a, b}
P = {S → aSb | ε}
S = Start Symbol

यह Grammar उन सभी strings को generate करती है जिनमें ‘a’ की संख्या ‘b’ की संख्या के बराबर होती है, जैसे: ab, aabb, aaabbb, आदि।

2️⃣ Derivation / व्युत्पत्ति

Derivation वह प्रक्रिया है जिसमें हम किसी Grammar के production rules को बार-बार लागू करके Terminals की String प्राप्त करते हैं।

उदाहरण:

Grammar: S → aSb | ε

Derive string “aabb”:

S ⇒ aSb
  ⇒ aaSbb
  ⇒ aabb

Leftmost Derivation:

जब हम हर बार सबसे बाएँ Non-terminal को बदलते हैं।

Rightmost Derivation:

जब हम हर बार सबसे दाएँ Non-terminal को बदलते हैं।

3️⃣ Parse Tree (व्युत्पत्ति वृक्ष)

Parse Tree Grammar के द्वारा उत्पन्न किसी string की derivation को tree के रूप में प्रदर्शित करता है।

उदाहरण:

Grammar: S → aSb | ε

String: aabb

        S
       / \
      a   S   b
         / \
        a   ε  b

यह tree दिखाता है कि string “aabb” कैसे grammar rules से उत्पन्न हुई।

4️⃣ भाषा का प्रकार / Type of Language

CFG Context-Free Languages (CFLs) को generate करता है, जो Pushdown Automata (PDA) द्वारा स्वीकार की जा सकती हैं।

Relation:

• Every Context-Free Grammar ⇄ Pushdown Automaton (PDA)
• हर PDA के लिए एक CFG मौजूद होती है जो उसी भाषा को generate करती है।

5️⃣ Context-Free Grammar के उदाहरण

• L₁ = {aⁿbⁿ | n ≥ 0}, Grammar: S → aSb | ε
• L₂ = {aⁿbᵐ | n, m ≥ 0}, Grammar: S → aS | B, B → bB | ε
• L₃ = {w wʳ | w ∈ {a,b}*}, Grammar: S → aSa | bSb | a | b | ε

6️⃣ Ambiguity in CFG / अस्पष्टता

किसी Context-Free Grammar को Ambiguous कहा जाता है यदि एक ही string को दो अलग-अलग Parse Trees द्वारा derive किया जा सकता है।

उदाहरण:

Grammar:

E → E + E | E * E | id

String: id + id * id इसके लिए दो अलग-अलग parse trees संभव हैं — इसलिए यह Grammar Ambiguous है।

7️⃣ CFG का उपयोग / Applications

• Compiler Design में Syntax Analysis के लिए।
• Programming Language Parser Construction में।
• XML, HTML और Data Markup Languages के लिए।
• Natural Language Processing (NLP) में Sentence Structure Analysis के लिए।

8️⃣ CFG के लाभ / Advantages

• भाषा संरचना को स्पष्ट रूप से परिभाषित करता है।
• Parser बनाना आसान।
• Nested और Recursive Structure को represent कर सकता है।

9️⃣ सीमाएँ / Limitations

• CFG में Ambiguity की समस्या होती है।
• Context-sensitive patterns को represent नहीं कर सकता।

निष्कर्ष / Conclusion

Context-Free Grammar प्रोग्रामिंग भाषाओं और Compiler Theory की नींव है। यह भाषाओं की hierarchical संरचना को समझने और Parsing Mechanism को डिजाइन करने में महत्वपूर्ण भूमिका निभाता है। हर CFG को Pushdown Automata द्वारा पहचाना जा सकता है, जिससे यह ऑटोमाटा सिद्धांत का एक अनिवार्य हिस्सा बनता है।