सीएफजी में विस्तार, यह क्या है?

Question

संदर्भ-मुक्त व्याकरण के लिए निम्न एक्सटेंशन पर विचार करें जो नियमों को बाएं हाथ में रखने की अनुमति देता है, गैर-टर्मिनल के दाईं ओर एक (या अधिक) टर्मिनल। यही है, फॉर्म के नियम:

A b -> ... 

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

स्पष्ट रूप से, यह अब CFG (टाइप -2) नहीं है। इसमें टाइप -1 शामिल है। लेकिन यह क्या हैं? वास्तव में पहले से ही 0 टाइप करें?

इस विशेष विस्तार को Prolog में Definite Clause ग्रामर dcg में अनुमति दी गई है। (गलतफहमी से बचने के लिए, मैं यहां प्रोलॉग के पूर्ण एक्सटेंशन पर विचार नहीं करता हूं। मैं मानता हूं कि टर्मिनल एक सीमित वर्णमाला से आते हैं और मनमानी शर्तों के बारे में नहीं मानते हैं, मैं भी प्रोलॉग के अतिरिक्त तर्कों पर विचार नहीं करता जिन्हें डीसीजी में अनुमति है, जो कि टाइप- । 0 पहले से ही)

---

संपादित करें: यहाँ विस्तार वर्णन करने के लिए एक सरल तरीका है: प्रपत्र की एक CFG नियम

A b -> <epsilon> 

Answer 1

Prolog के DCG रीतिवाद के संबंध में मेरे सवाल का जवाब करने के लिए, इस विस्तार अब एक semicontext कहा जाता है।देखें N253 DIN Draft for DCGs 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08

को देखते हुए

a1, [b] --> ... . 

a2, [b,b] --> ... . 

टर्मिनल-अनुक्रम [b] अब एक semicontext, साथ ही टर्मिनल-अनुक्रम [b,b] है।

एक ही टर्मिनल अनुक्रम अब शासन के अंत में दिखाई देते हैं, हम एक संदर्भ के लिए होता है चाहेंगे:

a3, [b,b] --> ..., [b,b]. 

तो "अर्द्ध" यहाँ का अर्थ है "आधा" - एक semigroup के लिए इसी तरह जहां बीजीय के आधे एक समूह पकड़ के गुण।

Answer 2

हाँ यह प्रकार 0 मुझे लगता है कि में जोड़े। पहले 3 प्रकार (3, 2 और 1) के लिए सिद्धांत यह है कि वे कमी नहीं कर सकते हैं। वे केवल जेनरेटिव हैं।

व्याकरण प्रकार 0. के भीतर है एक context-sensitive grammar (टाइप -1) फार्म के नियम हैं:

यहाँ आप यहाँ एक आंशिक जवाब है, इसलिए इसमें प्रकार 0.

Answer 3

है एप्सिलॉन में एक टर्मिनल बदल सकता है wAx -> wBx जहां डब्ल्यू और एक्स टर्मिनलों और गैर-टर्मिनलों के तार हैं, और बी खाली नहीं है। ध्यान दें कि चूंकि बी खाली नहीं है, |wAx| <= |wBx|। आपके व्याकरण के पास Ax -> z के नियम हैं जहां z टर्मिनल और गैर-टर्मिनलों की एक स्ट्रिंग है और खाली हो सकती है, और x को हटाया जा सकता है। यह सीएसजी के दो सिद्धांतों का उल्लंघन करता है।

Unsatisfyingly, मैं दो बातें का जवाब नहीं दिया:

• भाषा अपने व्याकरण टाइप -1 द्वारा उत्पन्न है? व्याकरण टाइप -0 है, लेकिन इसका मतलब यह नहीं है कि भाषा टाइप -1 नहीं हो सकती है। उदाहरण के लिए, सीएफजी (टाइप -2) द्वारा नियमित भाषाओं (टाइप -3) का वर्णन किया जा सकता है।

• भाषा recursive है? यह तब से महत्वपूर्ण है, यदि हां, तो भाषा निर्णायक है (रोकथाम की समस्या से पीड़ित नहीं है)।

  मैं वर्तमान में दूसरे बिंदु के लिए सबूत का प्रयास कर रहा हूं, लेकिन शायद यह मेरी क्षमता से परे है।