Equivalence (formal languages)
औपचारिक भाषा सिद्धांत में, दो व्याकरणों की कमजोर समतुल्यता का अर्थ है कि वे तारों का एक ही समूह उत्पन्न करते हैं, अर्थात। कि वे जो औपचारिक भाषा उत्पन्न करते हैं वह समान है। संकलक सिद्धांत में धारणा को मजबूत (या संरचनात्मक) समतुल्यता से अलग किया जाता है, जिसका अतिरिक्त अर्थ है कि दो पार्स ट्री यथोचित रूप से समान हैं क्योंकि दोनों को एक ही शब्दार्थिक व्याख्या दी जा सकती है। विजय-शंकर और वीर (1994) दर्शाते हैं कि रैखिक अनुक्रमित व्याकरण, संयुक्त श्रेणी व्याकरण, वृक्ष-संलग्न व्याकरण और प्रमुख व्याकरण कमजोर रूप से समतुल्य औपचारिकताएं हैं, जिसमें वे सभी एक ही स्ट्रिंग भाषाओं को परिभाषित करते हैं। दूसरी ओर, यदि दो व्याकरण व्युत्पत्ति वृक्षों का एक ही समूह उत्पन्न करते हैं (या अधिक सामान्य रूप से, अमूर्त वाक्य रचना वस्तुओं का एक ही समूह), तो दोनों व्याकरण दृढ़ता से समतुल्य हैं। चॉम्स्की (1963) ने मजबूत समतुल्यता की धारणा का परिचय दिया और तर्क दिया कि व्याकरण की औपचारिकताओं की तुलना करते समय केवल मजबूत समतुल्यता ही प्रासंगिक है। कोर्नाई और पुल्लम (1990) और मिलर (1994) मजबूत समतुल्यता की एक परिष्कृत धारणा प्रदान करते हैं जो विभिन्न औपचारिकताओं द्वारा दिए गए वाक्यात्मक विश्लेषणों के बीच समरूप संबंधों की अनुमति देता है। योशिनागा, मियाओ और त्सुजी (2002) इस बात का प्रमाण देते हैं कि किसी भी एल. टी. ए. जी. औपचारिकता के लिए, एक प्रबल समतुल्य एच. पी. एस. जी. है। संदर्भ-मुक्त व्याकरण का उदाहरण एक उदाहरण के रूप में, बैकस-नौर रूप में दिए गए निम्नलिखित दो संदर्भ-मुक्त व्याकरणों पर विचार करेंः <अभिव्यक्ति>:: = <अभिव्यक्ति> + "<अभिव्यक्ति>। <अभिव्यक्ति>-" <अभिव्यक्ति>। <अभिव्यक्ति>। "x"। "y"। "z"। "1"। "2"। "3"। "(" <अभिव्यक्ति> ")" <अभिव्यक्ति>: = <शब्द>। <अभिव्यक्ति> "+" <शब्द>। <अभिव्यक्ति> "-" <पद> <पद>:: = <कारक>। <पद> सभी अंकगणितीय अभिव्यक्तियों का समूह जो चर "x", "y", "z", स्थिरांक "1", "2", "3", प्रचालक "+", "-", "*", "/", और कोष्ठक "(" और ")" से बनाया जा सकता है। हालांकि, दूसरे व्याकरण का एक ठोस वाक्यविन्यास वृक्ष हमेशा संचालन के सामान्य क्रम को दर्शाता है, जबकि पहले व्याकरण से एक वृक्ष की आवश्यकता नहीं है। उदाहरण स्ट्रिंग "1 + 2 * 3" के लिए, चित्र का दाहिना भाग दूसरे व्याकरण के साथ अपने अद्वितीय पार्स ट्री को दिखाता है; पोस्टफिक्स क्रम में इस ट्री का मूल्यांकन करने से उचित मान मिलेगा, 7। इसके विपरीत, बाईं तस्वीर का हिस्सा पहले व्याकरण के साथ उस स्ट्रिंग के लिए पार्स ट्री में से एक को दिखाता है; इसे पोस्टफिक्स क्रम में मूल्यांकन करने से 9 मिलेगा। चूँकि दूसरा व्याकरण बाएं चित्र भाग के अनुरूप एक वृक्ष उत्पन्न नहीं कर सकता है, जबकि पहला व्याकरण कर सकता है, दोनों व्याकरण दृढ़ता से समतुल्य नहीं हैं। भाषाविज्ञान में, एक व्याकरण की कमजोर उत्पादक क्षमता को इसके द्वारा उत्पन्न सभी तारों के समूह के रूप में परिभाषित किया जाता है, जबकि एक व्याकरण की मजबूत उत्पादक क्षमता इसके द्वारा उत्पन्न "संरचनात्मक विवरणों" के समूह को संदर्भित करती है। नतीजतन, दो व्याकरणों को कमजोर समतुल्य माना जाता है यदि उनकी कमजोर उत्पादक क्षमताएं मेल खाती हैं; मजबूत समतुल्यता के लिए समान। उत्पादक क्षमता की धारणा 1963 में नोम चॉम्स्की द्वारा पेश की गई थी। टिप्पणियाँ संदर्भ औपचारिक भाषाएँ