Conjunctive grammar
संयुग्म व्याकरण औपचारिक भाषा सिद्धांत में अध्ययन किए गए औपचारिक व्याकरणों का एक वर्ग है। वे एक संयोजन संचालन के साथ मूल प्रकार के व्याकरण, संदर्भ-मुक्त व्याकरण का विस्तार करते हैं। स्पष्ट संयोजन के अलावा, संयुग्म व्याकरण एक गैर-अंतिम प्रतीक के लिए कई नियमों द्वारा दर्शाए गए अंतर्निहित विच्छेदन की अनुमति देते हैं, जो संदर्भ-मुक्त व्याकरण में व्यक्त होने वाला एकमात्र तार्किक संयोजक है। संयोजन का उपयोग, विशेष रूप से, भाषाओं के प्रतिच्छेदन को निर्दिष्ट करने के लिए किया जा सकता है। संयुग्म व्याकरण का एक और विस्तार जिसे बूलियन व्याकरण के रूप में जाना जाता है, अतिरिक्त रूप से स्पष्ट निषेध की अनुमति देता है। एक संयुग्म व्याकरण के नियम उस रूप के होते हैं जहां एक अंतहीन होता है और..., और (क्रमशः अंतस्थ और अंतहीन प्रतीकों के सीमित समूह) में प्रतीकों से बने तार होते हैं। अनौपचारिक रूप से, ऐसा नियम इस बात पर जोर देता है कि प्रत्येक स्ट्रिंग जो प्रत्येक वाक्य रचना शर्तों को संतुष्ट करती है, इसलिए द्वारा परिभाषित शर्त को संतुष्ट करती है। औपचारिक परिभाषा एक संयुग्म व्याकरण को 4-टुपल द्वारा परिभाषित किया जाता है जहां एक परिमित सेट होता है; प्रत्येक तत्व को एक गैर-अंतिम प्रतीक या एक चर कहा जाता है। प्रत्येक चर वाक्य में एक अलग प्रकार के वाक्यांश या खंड का प्रतिनिधित्व करता है। चर को कभी-कभी वाक्य रचना की श्रेणियाँ भी कहा जाता है। टर्मिनलों का एक सीमित समूह है, जो वाक्य की वास्तविक सामग्री को अलग करता है। टर्मिनलों का समूह व्याकरण द्वारा परिभाषित भाषा की वर्णमाला है। प्रस्तुतियों का एक सीमित समूह है, जिसमें से प्रत्येक कुछ और के लिए है। के सदस्यों को व्याकरण के नियम या रचना कहा जाता है। प्रारंभ चर (या प्रारंभ प्रतीक) है, जिसका उपयोग पूरे वाक्य (या कार्यक्रम) का प्रतिनिधित्व करने के लिए किया जाता है। यह एक तत्व होना चाहिए। एक ही रेखा पर एक ही बाएं हाथ की ओर के लिए सभी दाहिने हाथ की भुजाओं को सूचीबद्ध करना आम बात है, उन्हें अलग करने के लिए। (पाइप प्रतीक) का उपयोग करना। नियम और इसलिए के रूप में लिखा जा सकता है। एक संयोजी व्याकरण द्वारा निर्दिष्ट भाषा की दो समतुल्य औपचारिक परिभाषाएँ मौजूद हैं। एक परिभाषा व्याकरण को संघ, प्रतिच्छेदन और संयोजन के साथ भाषा समीकरणों की एक प्रणाली के रूप में प्रस्तुत करने और इसके सबसे कम समाधान पर विचार करने पर आधारित है। दूसरी परिभाषा चॉम्स्की की संदर्भ-मुक्त व्याकरण की उत्पादक परिभाषा को सामान्यीकृत करती है जिसमें संयोजन और संयोजन पर शब्दों के पुनर्लेखन का उपयोग किया जाता है। व्युत्पत्ति द्वारा परिभाषा किसी भी स्ट्रिंग के लिए, हम सीधे यील्ड कहते हैं, लिखा जाता है, यदि या तो ऐसा कोई नियम है और, या ऐसी कोई स्ट्रिंग मौजूद है जो और है। हम कहते हैं कि किसी भी स्ट्रिंग के लिए उत्पन्न होता है, लिखा जाता है, यदि ऐसा है। व्याकरण की भाषा उन सभी तारों का समूह है जो यह उत्पन्न करती है। उदाहरण व्याकरण, प्रस्तुतियों के साथ,,,,, संयुग्म है। एक विशिष्ट व्युत्पत्ति यह है कि यह दिखाया जा सकता है। भाषा संदर्भ-मुक्त नहीं है, जो संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा द्वारा साबित होती है। पार्सिंग एल्गोरिदम हालांकि संयुग्म व्याकरण की अभिव्यंजक शक्ति संदर्भ-मुक्त व्याकरण की तुलना में अधिक है, संयुग्म व्याकरण बाद के कुछ को बनाए रखते हैं। सबसे महत्वपूर्ण बात यह है कि मुख्य संदर्भ-मुक्त पार्सिंग एल्गोरिदम के सामान्यीकरण हैं, जिनमें रैखिक-समय पुनरावर्ती वंश, घन-समय सामान्यीकृत एलआर, घन-समय कॉक-कसामी-यंगर के साथ-साथ वैलिएंट का एल्गोरिदम मैट्रिक्स गुणन के रूप में तेजी से चल रहा है। सैद्धांतिक गुण एक ऐसा गुण जो पहले से ही संदर्भ-मुक्त भाषाओं या उनके सीमित चौराहों के लिए अनिर्णायक है, संयोजन व्याकरण के लिए भी अनिर्णायक होना चाहिए; इनमें शामिल हैंः खालीपन, सीमितता, नियमितता, संदर्भ-स्वतंत्रता, समावेश और समानता। संयुग्म भाषाओं का परिवार संघ, प्रतिच्छेदन, संयोजन और क्लेन स्टार के तहत बंद है, लेकिन स्ट्रिंग समरूपता, उपसर्ग, प्रत्यय और सबस्ट्रिंग के तहत नहीं। पूरक के तहत और ε-मुक्त स्ट्रिंग समरूपता के तहत बंद होना अभी भी खुली समस्याएं हैं (2001 तक)। एक-अक्षर वर्णमाला पर व्याकरण की अभिव्यंजक शक्ति पर शोध किया गया है। इस कार्य ने अधिक सामान्य रूप के भाषा समीकरणों के अध्ययन के लिए एक आधार प्रदान किया। सिंक्रोनाइज़्ड अल्टरनेटिंग पुशडाउन ऑटोमेटा आईज़िकोविट्ज़ और कामिंस्की ने पुशडाउन ऑटोमेटा (पीडीए) का एक नया वर्ग पेश किया जिसे सिंक्रोनाइज़्ड अल्टरनेटिंग पुशडाउन ऑटोमेटा (एसएपीडीए) कहा जाता है। उन्होंने इसे उसी तरह संयुग्म व्याकरण के बराबर साबित किया जैसे गैर-निर्धारक पी. डी. ए. संदर्भ-मुक्त व्याकरण के बराबर हैं। टिप्पणियाँ संदर्भ बाहरी लिंक तकनीकी रिपोर्ट संस्करण (पी. डी. एफ.) औपचारिक भाषाएँ