प्रसंग-मुक्त व्याकरण परिचय

Definition - एक संदर्भ-मुक्त व्याकरण (सीएफजी) जिसमें व्याकरण के नियमों का एक सीमित सेट है, एक चौगुनी है (N, T, P, S) कहाँ पे

  • N गैर-टर्मिनल प्रतीकों का एक सेट है।

  • T टर्मिनलों का एक सेट है जहां N ∩ T = NULL.

  • P नियमों का एक सेट है, P: N → (N ∪ T)*, अर्थात्, उत्पादन नियम का बायाँ भाग P इसका कोई सही संदर्भ या कोई संदर्भ नहीं है।

  • S प्रारंभ प्रतीक है।

Example

  • व्याकरण ({ए}, {ए, बी, सी}, पी, ए), पी: ए → एए, ए → एसीसी।
  • व्याकरण ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → {
  • व्याकरण ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, एफ → 00F | ε

व्युत्पत्ति वृक्ष की उत्पत्ति

एक व्युत्पत्ति वृक्ष या पार्स ट्री एक क्रमबद्ध जड़ वाला पेड़ है जो एक संदर्भ-मुक्त व्याकरण से व्युत्पन्न शब्दार्थ सूचना का रेखांकन करता है।

प्रतिनिधित्व तकनीक

  • Root vertex - प्रारंभ चिह्न द्वारा लेबल किया जाना चाहिए।

  • Vertex - एक गैर-टर्मिनल प्रतीक द्वारा लेबल किया गया।

  • Leaves - एक टर्मिनल प्रतीक या terminal द्वारा लेबल किया गया।

यदि S → x 1 x 2 …… x n एक CFG में एक उत्पादन नियम है, तो पार्स ट्री / व्युत्पत्ति ट्री इस प्रकार होगा -

एक व्युत्पत्ति पेड़ को खींचने के लिए दो अलग-अलग दृष्टिकोण हैं -

Top-down Approach −

  • शुरुआती प्रतीक के साथ शुरू होता है S

  • प्रस्तुतियों का उपयोग करते हुए पेड़ों की पत्तियों तक जाता है

Bottom-up Approach −

  • पेड़ की पत्तियों से शुरू होता है

  • जड़ के ऊपर की ओर बढ़ता है जो शुरुआती प्रतीक है S

पेड़ की व्युत्पत्ति या उपज

परसे के पेड़ की व्युत्पत्ति या पैदावार अंतिम स्ट्रिंग है, जो पेड़ों की पत्तियों के लेबल को बायीं ओर से खींचकर नल की अनदेखी करके प्राप्त की जाती है। हालांकि, यदि सभी पत्तियां अशक्त हैं, तो व्युत्पत्ति अशक्त है।

Example

एक CFG {N, T, P, S} होने दें

N = {S}, T = {a, b}, प्रारंभिक प्रतीक = S, P = S → SS | aSb | ε

उपरोक्त सीएफजी में से एक व्युत्पत्ति है "अबबब"

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

सजातीय रूप और आंशिक व्युत्पन्न वृक्ष

आंशिक व्युत्पत्ति वृक्ष एक व्युत्पत्ति वृक्ष / तोते के पेड़ का एक उप-वृक्ष है, जैसे या तो उसके सभी बच्चे उप-वृक्ष में हैं या उनमें से कोई भी उप-वृक्ष में नहीं है।

Example

यदि किसी भी CFG में प्रोडक्शंस हैं -

एस → एबी, ए → एएए | B, B → Bb | ε

आंशिक व्युत्पत्ति पेड़ निम्नलिखित हो सकता है -

यदि एक आंशिक व्युत्पत्ति के पेड़ में जड़ एस होता है, तो इसे ए कहा जाता है sentential form। उपर्युक्त उप-वृक्ष भी भावुक रूप में है।

एक स्ट्रिंग के सबसे बाएँ और दाएँ व्युत्पत्ति

  • Leftmost derivation - प्रत्येक चरण में सबसे बाईं ओर के उत्पादन को लागू करके एक बाईं ओर की व्युत्पत्ति प्राप्त की जाती है।

  • Rightmost derivation - प्रत्येक चरण में सबसे सही चर पर उत्पादन लागू करके एक सही व्युत्पत्ति प्राप्त की जाती है।

Example

सीएफजी में उत्पादन नियमों का कोई भी सेट होने दें

X → X + X | X * X | X | ए

एक वर्णमाला {a} पर।

स्ट्रिंग के लिए सबसे बाईं व्युत्पत्ति "a+a*a" हो सकता है -

एक्स → एक्स + एक्स → ए + एक्स → ए + एक्स * एक्स → ए + ए * एक्स → ए + ए * ए

उपरोक्त स्ट्रिंग की स्टेपवाइज व्युत्पत्ति नीचे दी गई है -

उपरोक्त स्ट्रिंग के लिए सबसे सही व्युत्पत्ति "a+a*a" हो सकता है -

एक्स → एक्स * एक्स → एक्स * ए → एक्स + एक्स * ए → एक्स + ए * ए → ए + ए * ए

उपरोक्त स्ट्रिंग की स्टेपवाइज व्युत्पत्ति नीचे दी गई है -

बाएँ और दाएँ पुनरावर्ती व्याकरण

एक संदर्भ-मुक्त व्याकरण में G, अगर फार्म में उत्पादन होता है X → Xa कहाँ पे X एक गैर-टर्मिनल है और ‘a’ टर्मिनलों की एक स्ट्रिंग है, इसे ए कहा जाता है left recursive production। वाम पुनरावर्ती उत्पादन वाले व्याकरण को a कहा जाता हैleft recursive grammar

और अगर एक संदर्भ-मुक्त व्याकरण में G, अगर वहाँ एक उत्पादन के रूप में है X → aX कहाँ पे X एक गैर-टर्मिनल है और ‘a’ टर्मिनलों की एक स्ट्रिंग है, इसे ए कहा जाता है right recursive production। सही पुनरावर्ती उत्पादन वाले व्याकरण को a कहा जाता हैright recursive grammar