क्या हम यह निर्धारित कर सकते हैं कि दी गई स्ट्रिंग संदर्भ-मुक्त व्याकरण द्वारा स्वीकार की गई है या नहीं? क्या यह समस्या समाधान योग्य है?

/ / में प्रकाशित साइबर सुरक्षा, EITC/IS/CCTF कम्प्यूटेशनल जटिलता थ्योरी फंडामेंटल्स, decidability, संदर्भ-मुक्त भाषाओं से संबंधित समस्याएं, परीक्षा समीक्षा

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

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

यह निर्धारित करने के लिए कि क्या दी गई स्ट्रिंग संदर्भ-मुक्त व्याकरण द्वारा स्वीकार की जाती है, हम विभिन्न एल्गोरिदम का उपयोग कर सकते हैं, जैसे कि CYK एल्गोरिदम या अर्ली एल्गोरिदम। ये एल्गोरिदम कुशलतापूर्वक जांचने के लिए गतिशील प्रोग्रामिंग तकनीकों का उपयोग करते हैं कि क्या कोई स्ट्रिंग व्याकरण के प्रारंभ प्रतीक से प्राप्त की जा सकती है।

उदाहरण के लिए, CYK एल्गोरिथ्म एक तालिका का निर्माण करता है जहां प्रत्येक सेल इनपुट स्ट्रिंग के एक सबस्ट्रिंग और गैर-टर्मिनलों के एक सेट का प्रतिनिधित्व करता है जो उस सबस्ट्रिंग को उत्पन्न कर सकता है। व्याकरण के उत्पादन नियमों के आधार पर तालिका को पुनरावृत्त रूप से भरकर, एल्गोरिदम यह निर्धारित करता है कि प्रारंभ प्रतीक संपूर्ण इनपुट स्ट्रिंग उत्पन्न कर सकता है या नहीं। यदि प्रारंभ चिह्न तालिका के शीर्ष-दाएँ कक्ष में दिखाई देता है, तो स्ट्रिंग व्याकरण द्वारा स्वीकार की जाती है; अन्यथा, ऐसा नहीं है.

निम्नलिखित उदाहरण पर विचार करें: मान लें कि हमारे पास उत्पादन नियमों के साथ एक संदर्भ-मुक्त व्याकरण है:
एस -> एबी
ए -> ए
बी -> बी

यदि हम यह निर्धारित करना चाहते हैं कि क्या स्ट्रिंग "ab" इस व्याकरण द्वारा स्वीकार की जाती है, तो हम CYK एल्गोरिदम लागू कर सकते हैं। एल्गोरिदम दो कोशिकाओं के साथ एक तालिका बनाता है, इनपुट स्ट्रिंग में प्रत्येक वर्ण के लिए एक। तालिका इस प्रकार दिखती है:

| 1 | 2 |
—+—+—+
1 | ए | एस |
—+—+—+
2 | | बी |
—+—+—+

नीचे की पंक्ति से शुरू करके, हम देख सकते हैं कि सेल (2,2) में गैर-टर्मिनल बी है, जो उत्पादन नियम बी -> बी द्वारा उत्पन्न होता है। शीर्ष पंक्ति की ओर बढ़ते हुए, हम पाते हैं कि सेल (1,2) में गैर-टर्मिनल एस है, जो उत्पादन नियम एस -> एबी द्वारा उत्पन्न होता है। अंत में, सेल (1,1) में गैर-टर्मिनल ए होता है, जो उत्पादन नियम ए -> ए द्वारा उत्पन्न होता है। चूँकि प्रारंभ चिह्न S शीर्ष-दाएँ कक्ष में दिखाई देता है, हम यह निष्कर्ष निकाल सकते हैं कि स्ट्रिंग "ab" व्याकरण द्वारा स्वीकार की गई है।

यह निर्धारित करने की समस्या कि क्या किसी दी गई स्ट्रिंग को संदर्भ-मुक्त व्याकरण द्वारा स्वीकार किया जाता है, निर्णायक है। CYK एल्गोरिथम या अर्ली एल्गोरिथम जैसे एल्गोरिदम का उपयोग कुशलतापूर्वक यह जांचने के लिए किया जा सकता है कि क्या कोई स्ट्रिंग व्याकरण के प्रारंभ प्रतीक से प्राप्त की जा सकती है। ये एल्गोरिदम तालिकाओं के निर्माण और स्ट्रिंग की स्वीकृति निर्धारित करने के लिए गतिशील प्रोग्रामिंग तकनीकों का उपयोग करते हैं।

संबंधित अन्य हालिया प्रश्न और उत्तर decidability:

डिसीडेबिलिटी में अधिक प्रश्न और उत्तर देखें

अधिक प्रश्न और उत्तर:

: अंतर्गत टैग