औपचारिक भाषा सिद्धांत और ऑटोमेटा
औपचारिक भाषाओं और उन्हें पहचानने वाली अमूर्त मशीनों का सिद्धांत, यह वर्णन करने के लिए शब्दावली प्रदान करता है कि एक भाषाई पैटर्न कितना जटिल है और कौन से एल्गोरिदम इसे संसाधित कर सकते हैं।
Definition
औपचारिक भाषा सिद्धांत व्याकरण द्वारा परिभाषित स्ट्रिंग के सेट का अध्ययन करता है, और ऑटोमेटा सिद्धांत उन अमूर्त मशीनों का अध्ययन करता है जो उन सेटों में सदस्यता का निर्णय करती हैं।
Scope
चॉम्स्की पदानुक्रम (नियमित, संदर्भ-मुक्त, संदर्भ-संवेदनशील, पुनरावर्ती गणनीय भाषाएँ), संबंधित व्याकरण और पहचानने वाले ऑटोमेटा — परिमित-राज्य मशीनें, पुशडाउन ऑटोमेटा और ट्यूरिंग मशीनें शामिल हैं। यह भाषा प्रसंस्करण के लिए प्रासंगिक समापन और निर्णयशीलता गुणों और पदानुक्रम में प्राकृतिक भाषा कहाँ स्थित है, इस प्रश्न को संबोधित करता है। पंपिंग लेम्मा और पूर्ण जटिलता प्रमाणों को प्राथमिक सामग्री के बजाय पृष्ठभूमि के रूप में माना जाता है।
Core questions
- चॉम्स्की पदानुक्रम के प्रत्येक स्तर के अनुरूप कौन सा ऑटोमेटन है?
- प्राकृतिक भाषा पदानुक्रम में कहाँ आती है, और यह तर्क क्यों दिया जाता है कि यह संदर्भ-मुक्त शक्ति से अधिक है?
- किसी भाषा वर्ग के लिए किसी ऑपरेशन के तहत बंद होने का क्या अर्थ है, और इंजीनियरिंग के लिए यह क्यों मायने रखता है?
Key concepts
- नियमित भाषा
- संदर्भ-मुक्त व्याकरण
- संदर्भ-संवेदनशील व्याकरण
- परिमित-राज्य ऑटोमेटन
- पुशडाउन ऑटोमेटन
- ट्यूरिंग मशीन
- समापन गुण
- हल्की संदर्भ-संवेदनशीलता
Key theories
- चॉम्स्की पदानुक्रम
- औपचारिक भाषाओं के चार नेस्टेड वर्ग, प्रत्येक एक प्रतिबंधित व्याकरण प्रकार द्वारा उत्पन्न होता है और एक संबंधित ऑटोमेटन द्वारा पहचाना जाता है, जो आवश्यक कम्प्यूटेशनल शक्ति द्वारा भाषाई निर्माणों को व्यवस्थित करता है।
- व्याकरण-ऑटोमेटन पत्राचार
- प्रत्येक व्याकरण वर्ग एक मशीन वर्ग के समतुल्य सिद्ध होता है — नियमित व्याकरण परिमित ऑटोमेटा के लिए, संदर्भ-मुक्त व्याकरण पुशडाउन ऑटोमेटा के लिए — जनरेटिव विवरणों को पहचान एल्गोरिदम से जोड़ता है।
History
चॉम्स्की के 1956 के पेपर ने इस तर्क के हिस्से के रूप में पदानुक्रम पेश किया कि परिमित-राज्य मॉडल प्राकृतिक भाषा के लिए अपर्याप्त थे। बाद के दशकों ने ऑटोमेटा पत्राचार को औपचारिक रूप दिया, और कम्प्यूटेशनल भाषाविदों ने बाद में दिखाया कि प्राकृतिक भाषा को अधिकतम 'हल्के संदर्भ-संवेदनशील' शक्ति की आवश्यकता होती है, जो संदर्भ-मुक्त से परे व्याकरण औपचारिकता को प्रेरित करती है।
Debates
- क्या प्राकृतिक भाषा संदर्भ-मुक्त है?
- स्विस जर्मन जैसी भाषाओं में क्रॉस-सीरियल निर्भरता का उपयोग यह तर्क देने के लिए किया गया था कि प्राकृतिक भाषा संदर्भ-मुक्त शक्ति से अधिक है, जिससे हल्के संदर्भ-संवेदनशीलता की धारणा व्यक्त करने के सही स्तर के रूप में सामने आई।
Key figures
- Noam Chomsky
- John Hopcroft
- Jeffrey Ullman
- Stephen Kleene
Related topics
Seminal works
- chomsky1956
- hopcroft2006
Frequently asked questions
- एक नियमित और एक संदर्भ-मुक्त भाषा में क्या अंतर है?
- नियमित भाषाओं को एक परिमित-राज्य ऑटोमेटन द्वारा सीमित मेमोरी के साथ पहचाना जा सकता है; संदर्भ-मुक्त भाषाओं को नेस्टेड संरचना, जैसे संतुलित कोष्ठक या एम्बेडेड क्लॉज़ को ट्रैक करने के लिए एक स्टैक (एक पुशडाउन ऑटोमेटन) की आवश्यकता हो सकती है।