चॉम्स्की पदानुक्रम
चॉम्स्की पदानुक्रम औपचारिक भाषाओं को चार नेस्टेड वर्गों में व्यवस्थित करता है, जिनमें से प्रत्येक को व्याकरण नियमों पर एक प्रतिबंध द्वारा परिभाषित किया गया है और एक अलग प्रकार की अमूर्त मशीन से मेल खाता है।
Definition
चॉम्स्की पदानुक्रम उत्पादन नियमों पर उत्तरोत्तर मजबूत प्रतिबंधों द्वारा औपचारिक व्याकरणों का एक वर्गीकरण है, जो सख्त समावेशन की एक श्रृंखला में नियमित, संदर्भ-मुक्त, संदर्भ-संवेदनशील और पुनरावर्ती गणनीय भाषा वर्गों को उत्पन्न करता है।
Scope
यह विषय चार व्याकरण प्रकारों को शामिल करता है - अप्रतिबंधित, संदर्भ-संवेदनशील, संदर्भ-मुक्त और नियमित - उनका सख्त समावेशन, और प्रत्येक स्तर के अनुरूप ऑटोमेटन मॉडल, अर्थात् ट्यूरिंग मशीन, लीनियर-बाउंडेड ऑटोमेटन, पुशडाउन ऑटोमेटन और परिमित ऑटोमेटन, साथ ही क्लोजर और निर्णयक्षमता गुण जो स्तरों को अलग करते हैं।
Core questions
- व्याकरण नियमों पर प्रतिबंध स्मृति और कंप्यूटिंग शक्ति की सीमाओं में कैसे परिवर्तित होते हैं?
- पदानुक्रम का प्रत्येक स्तर अगले में सख्ती से क्यों समाहित है?
- प्रत्येक व्याकरण प्रकार के अनुरूप कौन सा ऑटोमेटन मॉडल है?
- पदानुक्रम में ऊपर जाने पर निर्णयक्षमता और क्लोजर गुण कैसे बदलते हैं?
Key theories
- व्याकरण-मशीन पत्राचार
- प्रत्येक व्याकरण वर्ग को एक विशिष्ट मशीन मॉडल द्वारा पहचाना जाता है - परिमित ऑटोमेटा द्वारा नियमित, पुशडाउन ऑटोमेटा द्वारा संदर्भ-मुक्त, लीनियर-बाउंडेड ऑटोमेटा द्वारा संदर्भ-संवेदनशील, और ट्यूरिंग मशीनों द्वारा अप्रतिबंधित - जो गणना के जनरेटिव और ऑपरेशनल विवरणों को जोड़ता है।
- भाषा वर्गों का सख्त समावेशन
- प्रत्येक स्तर अपने नीचे वाले को ठीक से समाहित करता है, जो ठोस अलग-अलग भाषाओं द्वारा देखा जाता है, इसलिए पदानुक्रम समतुल्य विवरणों के संग्रह के बजाय बढ़ती अभिव्यंजक शक्ति की एक वास्तविक सीढ़ी है।
Clinical relevance
पदानुक्रम औपचारिक भाषा सिद्धांत का आयोजन मानचित्र है: यह प्रोग्रामिंग भाषाओं, क्वेरी भाषाओं और प्रोटोकॉल विनिर्देशों के डिजाइनरों को बताता है कि पैटर्न के एक दिए गए वर्ग को कितनी मशीनरी की आवश्यकता है, और यह इस बात के बीच की सीमा को निर्धारित करता है कि क्या निर्णय योग्य है और क्या केवल पहचानने योग्य है।
History
चॉम्स्की ने 1950 के दशक के अंत में प्राकृतिक-भाषा वाक्यविन्यास के औपचारिक मॉडल की तलाश करते हुए पदानुक्रम का प्रस्ताव रखा, और 1960 के दशक में ऑटोमेटा सिद्धांत के परिपक्व होने के साथ मशीन पत्राचार स्थापित किए गए, जिसमें मायहिल द्वारा लीनियर-बाउंडेड ऑटोमेटा पेश किए गए और कुरोदा द्वारा संदर्भ-संवेदनशील स्तर को स्पष्ट किया गया।
Key figures
- Noam Chomsky
- Marcel-Paul Schützenberger
- John Myhill
Related topics
Seminal works
- hopcroft2006
- sipser2013
Frequently asked questions
- चॉम्स्की पदानुक्रम के चार स्तर क्या हैं?
- सबसे कम से सबसे शक्तिशाली तक वे नियमित भाषाएँ (प्रकार 3), संदर्भ-मुक्त भाषाएँ (प्रकार 2), संदर्भ-संवेदनशील भाषाएँ (प्रकार 1), और पुनरावर्ती गणनीय भाषाएँ (प्रकार 0) हैं। प्रत्येक स्तर व्याकरण नियमों पर प्रतिबंधों को शिथिल करता है और अधिक स्मृति वाली मशीन के अनुरूप होता है।
- क्या प्राकृतिक भाषा चॉम्स्की पदानुक्रम द्वारा कैप्चर की जाती है?
- पदानुक्रम मूल रूप से भाषाविज्ञान से प्रेरित था, लेकिन अधिकांश भाषाविद् यह निष्कर्ष निकालते हैं कि प्राकृतिक भाषाएँ संदर्भ-मुक्त नहीं हैं, जो अक्सर हल्के संदर्भ-संवेदनशील नामक स्तर पर स्थित होती हैं। पदानुक्रम कंप्यूटर विज्ञान में मौलिक बना हुआ है, भले ही मानव भाषा इसमें केवल शिथिल रूप से फिट बैठती हो।