मैं इस सीएफजी में सीवाईके एल्गोरिदम कैसे लागू करूं?

सीएफजी जी होने दें:

S −→ AB|BA|AC|BD|EE
A −→ a
B −→ b
C −→ EB
D −→ EA
E −→ AB|BA|AC|BD|EE

यह निर्धारित करने के लिए कि क्या aabbab भाषा का हिस्सा है या नहीं, यह निर्धारित करने के लिए मैं CYK एल्गोरिदम का उपयोग कैसे करूं?

यह मेरे नोट्स में छद्म कोड है:

  for i in 1 .. n
     V[i,1] = { A | A -> x[i] }
  for j in 2..n
     for i in 1 .. n-j+1
        {
          V[i,j] = phi
          for k in 1 .. j-1
             V[i,j] = V[i,j] union { A | A -> BC where B in V[i,k]
                                                 and   C in V[i+k,j-k]}
        }

लेकिन मुझे समझ में नहीं आ रहा है कि उत्तर त्रिकोणीय आकार के ऊपर कैसे हो रहा है।

उदाहरण के लिए,

V[i,j]               i
         1(b)   2(a)   3(a)   4(b)   5(a)

      1  B      A,C    A,C    B      A,C

      2  S,A    B      S,C    S,A
  j
      3  phi    B      B

      4  phi    S,A,C

      5  S,A,C
         ^
         |_ accept
0

1 उत्तर

छद्म कोड [*] चार्ट बनाने के लिए एल्गोरिदम को लागू करने का तरीका बताता है।

[i, j] जोड़ी इनपुट के एक सबस्ट्रिंग को संदर्भित करती है जो i th प्रतीक से शुरू होती है और j प्रतीकों के लिए विस्तारित होती है। तो [2, 3] प्रतीक 3 से शुरू होने वाले 3-प्रतीक सबस्ट्रिंग को संदर्भित करता है। यदि आपका इनपुट baaba है, तो [2, 3] बीच में aab को संदर्भित करता है। (इंडेक्स 1-आधारित हैं, 0-आधारित नहीं हैं।)

चार्ट एक त्रिकोण बनाता है क्योंकि आपके पास एक सबस्ट्रिंग नहीं हो सकती है जो इनपुट से अधिक है। यदि इनपुट 5 प्रतीकों लंबा है, तो आपके पास [1, 5] में कोई मान हो सकता है, लेकिन आपके पास [2, 5] नहीं हो सकता है क्योंकि वह ' अब एक सबस्ट्रिंग का संदर्भ लें। तो प्रत्येक पंक्ति त्रिभुज बनाने, इससे पहले पंक्ति से एक बॉक्स छोटा है।

V[i, j] refers to a box in the chart. Each box is the set of non-terminals that may have produced the substring described by [i, j].

एल्गोरिदम चोम्स्की सामान्य रूप में व्याकरण पर निर्भर करता है। सीएनएफ में, प्रत्येक उत्पादन का दाहिने तरफ या तो एक टर्मिनल प्रतीक या दो गैर-टर्मिनल प्रतीकों हैं। (एक और एल्गोरिदम है जो संदर्भ-मुक्त व्याकरण को सीएनएफ में बदल सकता है।)

असल में, आप इनपुट के सभी 1-प्रतीक सबस्ट्रिंग के साथ शुरू करते हैं। आपके छद्म कोड में पहला लूप आपके चार्ट के शीर्ष पंक्ति ( j == 1 ) को भर देता है। यह व्याकरण में सभी प्रस्तुतियों को देखता है, और, यदि उत्पादन का दाहिने तरफ उस प्रतीक से मेल खाता है, तो उस उत्पादन के बाईं तरफ गैर-टर्मिनल सेट में जोड़ा जाता है V [i, 1] । (आपका उदाहरण पहली पंक्ति में कुछ फर्जी प्रविष्टियां प्रतीत होता है। {ए, सी} सेट केवल {ए} होना चाहिए।)

तब एल्गोरिदम शेष पंक्तियों के माध्यम से आगे बढ़ता है, जो सभी संभावित प्रस्तुतियों की तलाश करता है जो संबंधित सबस्ट्रिंग का उत्पादन कर सकते हैं। वर्तमान सबस्ट्रिंग को दो में विभाजित करने के प्रत्येक संभावित तरीके के लिए, यह एक समान उत्पादन की तलाश में है। इसमें पिछली पंक्तियों पर कुछ बक्से से गैर-टर्मिनलों के जोड़े को जोड़ना और जांच करना शामिल है कि उस जोड़ी का उत्पादन करने वाले कोई प्रोडक्शन हैं, इस प्रकार उस बॉक्स के लिए गैर-टर्मिनलों का एक सेट बनाते हैं।

यदि अंतिम पंक्ति में बॉक्स एक सेट के साथ समाप्त होता है जिसमें प्रारंभ प्रतीक होता है, तो इनपुट व्याकरण के अनुसार मान्य होता है। सहजता से, यह कहता है कि प्रारंभ प्रतीक पहले प्रतीक पर शुरू होने वाली सबस्ट्रिंग बनाने और पूरी लंबाई के लिए आगे बढ़ने के लिए एक वैध उत्पादन है।

[*] ऐसा लगता है कि प्रश्न में दिखाए गए छद्म कोड में कुछ प्रतिलेखन त्रुटियां हैं। विवरण सही प्राप्त करने के लिए आप एक आधिकारिक स्रोत से परामर्श करना चाहेंगे।

0
जोड़ा