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