स्वचालित यंत्र और औपचारिक भाषाएँ
स्वचालित यंत्र और औपचारिक भाषा सिद्धांत बढ़ती शक्ति की आदर्श मशीनों और स्ट्रिंग के वर्गों, या भाषाओं का अध्ययन करता है, जिन्हें प्रत्येक पहचान सकता है, यह एक सटीक गणितीय विवरण देता है कि एक पैटर्न क्या होता है और उसे पहचानने के लिए क्या आवश्यक है।
Definition
एक औपचारिक भाषा एक निश्चित वर्णमाला पर परिमित स्ट्रिंग का एक सेट है, और एक स्वचालित यंत्र एक अमूर्त कंप्यूटिंग उपकरण है जिसकी स्वीकार्य गणनाएँ ऐसी भाषा को परिभाषित करती हैं; यह क्षेत्र भाषाओं को सबसे सरल प्रकार के स्वचालित यंत्र या व्याकरण द्वारा वर्गीकृत करता है जो उन्हें उत्पन्न या पहचानता है।
Scope
यह क्षेत्र परिमित स्वचालित यंत्र और नियमित भाषाओं, पुशडाउन स्वचालित यंत्र और संदर्भ-मुक्त भाषाओं, ग्रामर को मशीन मॉडल से जोड़ने वाली चॉम्स्की पदानुक्रम, भाषा वर्गों के समापन और निर्णय गुणों, और अनंत शब्दों और वृक्षों को संसाधित करने वाले स्वचालित यंत्रों को शामिल करता है, साथ ही उनके साथ आने वाले बीजगणितीय और तार्किक लक्षण वर्णन भी।
Sub-topics
Core questions
- परिमित स्मृति वाली मशीन किन भाषाओं को पहचान सकती है, और किन भाषाओं को नहीं पहचान सकती?
- चॉम्स्की पदानुक्रम के विभिन्न स्तरों पर व्याकरण और मशीन मॉडल कैसे मेल खाते हैं?
- भाषा वर्ग के बारे में कौन से प्रश्न, जैसे शून्यता या तुल्यता, एल्गोरिथम रूप से निर्णायक हैं?
- स्वचालित यंत्र अनंत शब्दों और वृक्षों तक कैसे विस्तारित होते हैं, और सत्यापन के लिए यह क्यों मायने रखता है?
Key theories
- नियतात्मक और गैर-नियतात्मक परिमित स्वचालित यंत्रों की तुल्यता
- प्रत्येक गैर-नियतात्मक परिमित स्वचालित यंत्र को सबसेट निर्माण द्वारा एक नियतात्मक में परिवर्तित किया जा सकता है जो उसी भाषा को स्वीकार करता है, इसलिए गैर-नियतात्मकता परिमित-स्थिति स्तर पर कोई पहचानने की शक्ति नहीं जोड़ती है, भले ही यह घातीय रूप से अधिक संक्षिप्त हो सकती है।
- क्लीने का प्रमेय
- परिमित स्वचालित यंत्रों द्वारा पहचानी जाने वाली भाषाएँ ठीक वही नियमित भाषाएँ हैं जो नियमित अभिव्यक्तियों द्वारा वर्णित हैं, जो सबसे सरल भाषा वर्ग के मशीन, बीजगणितीय और व्याकरणिक विचारों को एक साथ जोड़ती हैं।
- चॉम्स्की पदानुक्रम
- नियमित, संदर्भ-मुक्त, संदर्भ-संवेदनशील और पुनरावर्ती रूप से गणनीय भाषाएँ एक सख्त समावेशन श्रृंखला बनाती हैं, प्रत्येक स्तर एक व्याकरण प्रकार और संबंधित स्मृति संरचना के एक स्वचालित यंत्र मॉडल से मेल खाता है।
Clinical relevance
परिमित स्वचालित यंत्र और नियमित अभिव्यक्तियाँ कंपाइलर, टेक्स्ट सर्च और प्रोटोकॉल विनिर्देश में लेक्सिकल विश्लेषण को शक्ति प्रदान करती हैं, जबकि संदर्भ-मुक्त व्याकरण प्रोग्रामिंग-भाषा पार्सिंग का आधार हैं; अनंत वस्तुओं पर स्वचालित यंत्र मॉडल चेकिंग का एल्गोरिथम कोर बनाते हैं, जहाँ एक प्रणाली को एक अस्थायी-तर्क विनिर्देश के विरुद्ध सत्यापित किया जाता है।
History
परिमित-स्थिति मॉडल 1940 के दशक में मैककुलोच और पिट्स के न्यूरल नेट से उभरे और क्लीने द्वारा 1951 के आसपास भाषा-सैद्धांतिक रूप दिया गया। राबिन और स्कॉट ने 1959 में गैर-नियतात्मक स्वचालित यंत्रों की शुरुआत की, जबकि 1950 के दशक के अंत से चॉम्स्की के व्याकरणों ने भाषा वर्गों को उस पदानुक्रम में व्यवस्थित किया जो अभी भी विषय को संरचित करता है।
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- एक परिमित स्वचालित यंत्र संतुलित कोष्ठकों को क्यों नहीं पहचान सकता?
- मनमाने ढंग से गहरी नेस्टिंग को पहचानने के लिए यह गिनने की आवश्यकता होती है कि कितने खुले हुए अभी भी बेजोड़ हैं, जो किसी भी निश्चित संख्या की स्थिति से अधिक हो सकते हैं। एक परिमित स्वचालित यंत्र में केवल सीमित स्मृति होती है, इसलिए यह गिनती क्षमता एक स्तर ऊपर, पुशडाउन स्वचालित यंत्रों और संदर्भ-मुक्त भाषाओं के साथ होती है।
- औपचारिक भाषा सिद्धांत का व्यावहारिक लाभ क्या है?
- यह इंजीनियरों को बताता है कि एक दिया गया उपकरण किन पैटर्न को व्यक्त कर सकता है। नियमित अभिव्यक्तियाँ टोकन के लिए पर्याप्त हैं लेकिन नेस्टेड संरचना के लिए नहीं, यही कारण है कि कंपाइलर नियमित लेक्सर और संदर्भ-मुक्त पार्सर के बीच काम को विभाजित करते हैं, और यही कारण है कि सत्यापन उपकरण अनंत शब्दों पर स्वचालित यंत्रों पर निर्भर करते हैं।