संदर्भ-मुक्त भाषाएँ और पुशडाउन ऑटोमेटा
संदर्भ-मुक्त व्याकरण नेस्टेड, पुनरावर्ती संरचना वाली भाषाओं को उत्पन्न करते हैं, और पुशडाउन ऑटोमेटा एक असीमित स्टैक के साथ एक परिमित नियंत्रण को बढ़ाकर ठीक इन्हीं भाषाओं को पहचानते हैं।
Definition
एक संदर्भ-मुक्त भाषा एक व्याकरण द्वारा उत्पन्न होती है जिसके नियम संदर्भ से स्वतंत्र रूप से एक एकल गैर-टर्मिनल प्रतीक को फिर से लिखते हैं, और इसे एक पुशडाउन ऑटोमेटन द्वारा पहचाना जाता है, जो एक स्टैक से सुसज्जित एक परिमित ऑटोमेटन है जो असीमित गहराई की लास्ट-इन, फर्स्ट-आउट मेमोरी प्रदान करता है।
Scope
यह विषय संदर्भ-मुक्त व्याकरण और व्युत्पत्तियों, पार्स ट्री और अस्पष्टता, पुशडाउन ऑटोमेटा के साथ संदर्भ-मुक्त व्याकरण की समानता, चॉम्स्की नॉर्मल फॉर्म जैसे सामान्य रूप, संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा, और क्लोजर और निर्णय गुणों को शामिल करता है जो इस वर्ग को नियमित भाषाओं से अलग करते हैं।
Core questions
- किस प्रकार के नेस्टेड या पुनरावर्ती पैटर्न को परिमित मेमोरी के बजाय स्टैक की आवश्यकता होती है?
- संदर्भ-मुक्त व्याकरण और पुशडाउन ऑटोमेटा शक्ति में समान क्यों हैं?
- एक व्याकरण कब अस्पष्ट होता है, और पार्सिंग के लिए अस्पष्टता क्यों मायने रखती है?
- संदर्भ-मुक्त भाषाओं के लिए कौन सी निर्णय समस्याएँ हल करने योग्य हैं, और कौन सी नहीं?
Key theories
- व्याकरण-ऑटोमेटन समानता
- एक भाषा संदर्भ-मुक्त होती है यदि और केवल यदि इसे किसी पुशडाउन ऑटोमेटन द्वारा स्वीकार किया जाता है, इसलिए जनरेटिव व्याकरण दृष्टिकोण और स्टैक-मशीन दृष्टिकोण भाषाओं के एक ही वर्ग का वर्णन करते हैं।
- चॉम्स्की नॉर्मल फॉर्म
- प्रत्येक संदर्भ-मुक्त व्याकरण को इस प्रकार फिर से लिखा जा सकता है कि प्रत्येक नियम या तो दो गैर-टर्मिनल या एक एकल टर्मिनल उत्पन्न करता है, एक सामान्य रूप जो पार्सिंग एल्गोरिदम और वर्ग के बारे में आगमनात्मक प्रमाणों का आधार है।
- संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा
- एक संदर्भ-मुक्त भाषा में प्रत्येक पर्याप्त लंबी स्ट्रिंग को इस प्रकार विभाजित किया जा सकता है कि उसके दो भाग एक साथ पंप किए जाते हैं, एक गुण जो स्टैक मेमोरी से अधिक की आवश्यकता वाली भाषाओं के लिए विफल रहता है और इस प्रकार उन्हें गैर-संदर्भ-मुक्त साबित करता है।
Clinical relevance
संदर्भ-मुक्त व्याकरण लगभग हर प्रोग्रामिंग भाषा और कई डेटा प्रारूपों के सिंटैक्स को निर्दिष्ट करते हैं, और पुशडाउन-शैली के पार्सिंग एल्गोरिदम इन व्याकरणों को कंपाइलर और इंटरप्रेटर के केंद्र में सिंटैक्टिक एनालाइज़र में बदल देते हैं, जिससे यह विषय प्रोग्रामिंग-भाषा प्रसंस्करण का सैद्धांतिक आधार बन जाता है।
History
चॉम्स्की ने 1950 के दशक के अंत में अपने पदानुक्रम के हिस्से के रूप में संदर्भ-मुक्त व्याकरणों की शुरुआत की, और उनका स्वतंत्र रूप से बैकस और नॉर द्वारा ALGOL प्रोग्रामिंग भाषा के सिंटैक्स को परिभाषित करने के लिए उपयोग किया गया। पुशडाउन ऑटोमेटा के साथ समानता और वर्ग का संरचनात्मक सिद्धांत 1960 के दशक में विकसित किया गया था।
Key figures
- Noam Chomsky
- John Backus
- Seymour Ginsburg
- Sheila Greibach
Related topics
Seminal works
- sipser2013
- hopcroft2006
Frequently asked questions
- प्रोग्रामिंग भाषा को पार्स करने के लिए स्टैक की आवश्यकता क्यों होती है?
- प्रोग्राम में नेस्टेड कंस्ट्रक्ट्स होते हैं जैसे कि कोष्ठक, ब्लॉक और फ़ंक्शन कॉल जिनकी मिलान गहराई असीमित होती है। एक स्टैक प्रत्येक अधूरी कंस्ट्रक्ट को रिकॉर्ड करता है और बंद होने पर उसे पॉप करता है, जो ठीक वही मेमोरी अनुशासन है जो एक पुशडाउन ऑटोमेटन प्रदान करता है और एक परिमित ऑटोमेटन में कमी होती है।
- एक व्याकरण के अस्पष्ट होने का क्या अर्थ है?
- एक व्याकरण अस्पष्ट होता है जब किसी स्ट्रिंग में एक से अधिक पार्स ट्री होते हैं, जिसका अर्थ है कि इसे वास्तव में विभिन्न संरचनाओं के साथ व्युत्पन्न किया जा सकता है। प्रोग्रामिंग भाषाओं के लिए अस्पष्टता अवांछनीय है क्योंकि यह कोड के अर्थ को अस्पष्ट छोड़ देती है, इसलिए भाषा डिजाइनर अस्पष्ट व्याकरण की तलाश करते हैं या अस्पष्टता-निवारण नियम जोड़ते हैं।