ऑटोमेटा सिद्धांत

Classes of automata

इस अवस्था आरेख द्वारा वर्णित ऑटोमेटन अवस्था S₁ में प्रारम्भ होता है, और इनपुट प्रतीकों के अनुसार 0 या 1 चिह्नित तीरों के बाद अवस्थाओंं को बदलता है जैसे वे आते हैं। दोगुना वृत्त S₁ को स्वीकार करने वाली अवस्था के रूप में चिह्नित करता है। चूँकि S₁ से लेकर स्वयं तक के सभी पथों में 0 चिन्हित तीरों की एक समान संख्या होती है, यह ऑटोमेटन 0s की सम संख्याओं वाली स्ट्रिंग्स को स्वीकार करता है।

ऑटोमेटा सिद्धांतसंक्षेप मशीनों और ऑटोमेटा का अध्ययन है, साथ ही उन कम्प्यूटेशनल समस्याओं का भी अध्ययन है जिन्हें उनका उपयोग करके हल किया जा सकता है। यह सैद्धांतिक कंप्यूटर विज्ञान में एक सिद्धांत है। ऑटोमेटा शब्द ग्रीक शब्द αὐτόματος से आया है, जिसका अर्थ है "स्व-अभिनय, स्व-इच्छाशक्ति, स्व-चालित"। ऑटोमेटन (बहुवचन में ऑटोमेटा) संक्षेप स्व-चालित कंप्यूटिंग उपकरण है जो स्वचालित रूप से संचालन के पूर्व निर्धारित अनुक्रम का अनुसरण करता है। अवस्थाओं की सीमित संख्या वाले ऑटोमेटन को परिमित ऑटोमेटन (एफए (FA)) या परिमित-अवस्था मशीन (एफएसएम (FSM)) कहा जाता है। दाईं ओर का आंकड़ा परिमित-अवस्था मशीन को दिखाता है, जो एक प्रसिद्ध प्रकार का ऑटोमेटन है। इस ऑटोमेटन में अवस्थाएँ (वृत्तों द्वारा चित्र में दर्शाई गई) और संक्रमण (तीर द्वारा दर्शाई गई) सम्मिलित हैं। चूंकि ऑटोमेटन इनपुट का प्रतीक देखता है, यह अपने संक्रमण फलन के अनुसार, किसी अन्य अवस्था में संक्रमण (या व्यतिक्रम) बनाता है, जो पिछली अवस्था और वर्तमान इनपुट प्रतीक को इसके तर्कों के रूप में लेता है।

ऑटोमेटा सिद्धांत औपचारिक भाषा सिद्धांत से निकटता से संबंधित है। इस संदर्भ में, ऑटोमेटा का उपयोग औपचारिक भाषाओं के सीमित निरूपण के रूप में किया जाता है जो अनंत हो सकती हैं। ऑटोमेटा को प्रायः औपचारिक भाषाओं के वर्ग द्वारा वर्गीकृत किया जाता है जिसे वे पहचान सकते हैं, जैसा कि चॉम्स्की पदानुक्रम में होता है, जो ऑटोमेटा के प्रमुख वर्गों के बीच नेस्टिंग संबंध का वर्णन करता है। संगणना, संकलक निर्माण, कृत्रिम बुद्धिमत्ता, पदव्याख्या और औपचारिक सत्यापन के सिद्धांत में ऑटोमेटा एक प्रमुख भूमिका निभाते हैं।

इतिहास

संक्षेप ऑटोमेटा के सिद्धांत को 20वीं शताब्दी के मध्य में परिमित ऑटोमेटा के संबंध में विकसित किया गया था। ऑटोमेटा सिद्धांत को प्रारम्भ में गणितीय प्रणाली सिद्धांत की शाखा माना जाता था, जो असतत-पैरामीटर प्रणाली के व्यवहार का अध्ययन करता था। पदार्थ प्रणालियों का वर्णन करने के लिए अवकल गणना के स्थान पर सूचना प्रणाली का वर्णन करने के लिए संक्षेप बीजगणित का उपयोग करके प्रणाली पर पिछले कार्य से ऑटोमेटा सिद्धांत में प्रारंभिक कार्य भिन्न होता है। परिमित-अवस्था ट्रांसड्यूसर के सिद्धांत को विभिन्न अनुसंधान समुदायों द्वारा अलग-अलग नामों से विकसित किया गया था। ट्यूरिंग मशीन की पहले की अवधारणा को अनंत-अवस्था ऑटोमेटा के नए रूपों जैसे पुशडाउन ऑटोमेटा के साथ अनुशासन में भी सम्मिलित किया गया था।

1956 में ऑटोमेटा अध्ययनों का प्रकाशन देखा गया, जिसमें क्लॉड शैनन, डब्ल्यू. रॉस एशबी, जॉन वॉन न्यूमैन, मार्विन मिंस्की, एडवर्ड एफ मूर और स्टीफन कोल क्लेन सहित वैज्ञानिकों द्वारा काम एकत्र किया गया था। इस खंड के प्रकाशन के साथ, "ऑटोमेटा सिद्धांत अपेक्षाकृत स्वायत्त अनुशासन के रूप में उभरा"। पुस्तक में क्लेन द्वारा नियमित घटनाओं, या नियमित भाषाओं के क्रम का वर्णन, और शैनन द्वारा ट्यूरिंग मशीन प्रोग्रमों में जटिलता की अपेक्षाकृत स्थिर माप सम्मिलित थी। उसी वर्ष, नोम चॉम्स्की ने चॉम्स्की पदानुक्रम, ऑटोमेटा और औपचारिक व्याकरण के बीच पत्राचार का वर्णन किया, और रॉस एशबी ने साइबरनेटिक्स का परिचय प्रकाशित किया, जो सुलभ पाठ्यपुस्तक है जो ऑटोमेटा और बुनियादी क्रम सिद्धांत का उपयोग करके जानकारी की व्याख्या करती है।

रैखिक परिबद्ध ऑटोमेटा के अध्ययन ने माइहिल-नेरोड प्रमेय का नेतृत्व किया, जो औपचारिक भाषा के नियमित होने के लिए आवश्यक और पर्याप्त स्थिति देती है, और भाषा के लिए न्यूनतम मशीन में अवस्थाओं की संख्या की सटीक गणना करती है। नियमित भाषाओं के लिए पम्पिंग लेम्मा, नियमितता प्रमाणों में भी उपयोगी, इस अवधि में माइकल ओ. राबिन और दाना स्कॉट द्वारा नियतात्मक और गैर-नियतात्मक परिमित ऑटोमेटा को कम्प्यूटेशनल तुल्यता के साथ सिद्ध किया गया था।

1960 के दशक में, "संरचना सिद्धांत" या "बीजगणितीय अपघटन सिद्धांत" के रूप में जाना जाने वाला बीजगणितीय परिणामों का एक समूह उभरा, जो अंतर्संबंध द्वारा छोटी मशीनों से अनुक्रमिक मशीनों की प्राप्ति से संबंधित था। जबकि किसी भी परिमित ऑटोमेटन को सार्वभौमिक गेट सेट का उपयोग करके अनुरूप किया जा सकता है, इसके लिए यह आवश्यक है कि अनुकरण परिपथ में मनमाने ढंग से जटिलता के लूप हों। संरचना सिद्धांत मशीनों की "लूप-मुक्त" प्राप्ति से संबंधित है। 1960 के दशक में कम्प्यूटेशनल जटिलता के सिद्धांत ने भी आकार लिया था। दशक के अंत तक, ऑटोमेटा सिद्धांत को "कंप्यूटर विज्ञान के शुद्ध गणित" के रूप में देखा जाने लगा था।

ऑटोमेटा

ऑटोमेटन की एक सामान्य परिभाषा क्या है, जो असतत समय-चरणों में कार्य करने के रूप में देखे जाने वाली प्रणाली की व्यापक परिभाषा को प्रतिबंधित करती है, इसके अवस्था व्यवहार और आउटपुट के साथ प्रत्येक चरण में केवल इसके अवस्था और इनपुट के अपरिवर्तनीय कार्यों द्वारा परिभाषित किया गया है।

अनौपचारिक विवरण

ऑटोमेटन तब चलता है जब उसे असतत (व्यक्तिगत) समय चरणों (या सिर्फ चरणों) में इनपुट का कुछ क्रम दिया जाता है। ऑटोमेटन प्रतीकों या अक्षरों के क्रम से चुने गए इनपुट को प्रोसेस करता है, जिसे इनपुट वर्णमाला कहा जाता है। ऑटोमेटन द्वारा किसी भी चरण में इनपुट के रूप में प्राप्त किए गए प्रतीक शब्द नामक प्रतीकों का अनुक्रम होते हैं। ऑटोमेटन में अवस्थाओं का क्रम होता है। ऑटोमेटन के रन के दौरान प्रत्येक क्षण ऑटोमेटन अपनी अवस्थाओं में से एक में होता है। जब ऑटोमेटन नया इनपुट प्राप्त करता है तो यह संक्रमण फलन के आधार पर दूसरे अवस्था (या संक्रमण) में चला जाता है जो पिछली अवस्था और वर्तमान इनपुट प्रतीक को मापदंडों के रूप में लेता है। उसी समय, एक अन्य फलन जिसे आउटपुट फलन कहा जाता है, आउटपुट वर्णमाला से पिछली अवस्था और वर्तमान इनपुट प्रतीक के अनुसार भी प्रतीक उत्पन्न करता है। ऑटोमेटन इनपुट शब्द के प्रतीकों को पढ़ता है और जब तक शब्द पूरी तरह से पढ़ा नहीं जाता है, तब तक अवस्थाओं के बीच संक्रमण होता है, अगर यह लंबाई में परिमित है, जिस बिंदु पर ऑटोमेटन रुक जाता है। जिस अवस्था में ऑटोमेटन रुकता है उसे अंतिम अवस्था कहा जाता है।

औपचारिक भाषा सिद्धांत का उपयोग करके ऑटोमेटन में संभावित अवस्था/इनपुट/आउटपुट अनुक्रमों की जांच करने के लिए, मशीन को प्रारंभिक अवस्था और स्वीकार करने वाले अवस्थाओं का क्रम सौंपा जा सकता है। फिर, इस पर निर्भर करते हुए कि प्रारंभिक अवस्था से प्रारम्भ होने वाला रन स्वीकार्य अवस्था में समाप्त होता है, ऑटोमेटन को इनपुट अनुक्रम को स्वीकार या अस्वीकार करने के लिए कहा जा सकता है। ऑटोमेटन द्वारा स्वीकृत सभी शब्दों के क्रम को ऑटोमेटन द्वारा मान्यता प्राप्त भाषा कहा जाता है। किसी भाषा को पहचानने वाली मशीन का एक परिचित उदाहरण इलेक्ट्रॉनिक लॉक है, जो सही कोड दर्ज करने के प्रयासों को स्वीकार या अस्वीकार करता है।

औपचारिक परिभाषा

ऑटोमेटन

ऑटोमेटन औपचारिक रूप से 5-टपल $M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle$ द्वारा प्रदर्शित किया जा सकता है जहां-

• $\Sigma$ प्रतीकों का परिमित क्रम है, जिसे ऑटोमेटन की इनपुट वर्णमाला कहा जाता है,
• $\Gamma$ प्रतीकों का एक और परिमित क्रम है, जिसे ऑटोमेटन की आउटपुट वर्णमाला कहा जाता है,
• $Q$ अवस्थाओं का क्रम है,
• $\delta$ अगली-अवस्था फलन या संक्रमण फलन $\delta :Q\times \Sigma \to Q$ मैपिंग अवस्था-इनपुट युग्म उत्तरवर्ती अवस्थाओं के लिए है,
• $\lambda$ आउटपुट के लिए अगला-आउटपुट फलन $\lambda :Q\times \Sigma \to \Gamma$ मैपिंग अवस्था-इनपुट युग्म है।

यदि $Q$ परिमित है, तो $M$ एक परिमित ऑटोमेटन है।

इनपुट शब्द

ऑटोमेटन प्रतीकों $a_{1}a_{2}...a_{n}$ की सीमित स्ट्रिंग पढ़ता है, जहां $a_{i}\in \Sigma$, जिसे इनपुट शब्द कहा जाता है। सभी शब्दों के समुच्चय को $\Sigma ^{*}$ द्वारा निरूपित किया जाता है

रन

अवस्थाओं का अनुक्रम $q_{0},q_{1},...,q_{n}$, जहां $q_{i}\in Q$ ऐसा है कि $0<i\leq n$ के लिए $q_{i}=\delta (q_{i-1},a_{i})$, अवस्था $q_{0}$ से प्रारम्भ होने वाले इनपुट $a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ पर ऑटोमेटन का रन है। दूसरे शब्दों में, सबसे पहले ऑटोमेटन प्रारंभिक अवस्था $q_{0}$ पर है, और इनपुट $a_{1}$ प्राप्त करता है। इनपुट स्ट्रिंग में $a_{1}$और प्रत्येक अनुवर्ती $a_{i}$ के लिए, ऑटोमेटन संक्रमण फलन $q_{i}$ के अनुसार अगली अवस्था $\delta (q_{i-1},a_{i})$ को चुनता है, जब तक कि अंतिम प्रतीक $a_{n}$ को पढ़ा नहीं जाता है, मशीन को रन की अंतिम अवस्था $q_{n}$ में छोड़ दिया जाता है। इसी तरह, प्रत्येक चरण पर, ऑटोमेटन आउटपुट फलन $\lambda (q_{i-1},a_{i})$ के अनुसार आउटपुट प्रतीक का उत्सर्जन करता है।

संपूर्ण इनपुट शब्द दिए जाने पर मशीन के व्यवहार का वर्णन करने के लिए संक्रमण फलन $\delta$ को आगमनात्मक रूप से ${\overline {\delta }}:Q\times \Sigma ^{*}\to Q$ में विस्तारित किया जाता है। सभी अवस्थाओं $q$ के लिए खाली स्ट्रिंग $\varepsilon$,${\overline {\delta }}(q,\varepsilon )=q$ के लिए, और स्ट्रिंग्स $wa$ के लिए जहां $a$ अंतिम प्रतीक है और $w$ शेष स्ट्रिंग, ${\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)$ (संभवतः खाली) है। आउटपुट फलन $\lambda$ को ${\overline {\lambda }}(q,w)$ में समान रूप से बढ़ाया जा सकता है, जो अवस्था $q$ से शब्द $w$ पर रन करने पर मशीन का पूरा आउटपुट देता है।

स्वीकर्ता

औपचारिक भाषाओं के सिद्धांत के साथ ऑटोमेटन का अध्ययन करने के लिए, ऑटोमेटन को स्वीकर्ता के रूप में माना जा सकता है, जो आउटपुट वर्णमाला और फलन $\Gamma$और $\lambda$ को प्रतिस्थापित करता है

• $q_{0}\in Q$, निर्दिष्ट प्रारंभ अवस्था, और
• $F$, $Q$ (अर्थात $F\subseteq Q$) की अवस्थाओं का एक क्रम स्वीकार अवस्थाओं को कहा जाता है।

यह निम्नलिखित को परिभाषित करने की अनुमति देता है-

स्वीकार करने वाला शब्द

शब्द $w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ ऑटोमेटन के लिए स्वीकार्य शब्द है यदि ${\overline {\delta }}(q_{0},w)\in F$, अर्थात, यदि पूरी स्ट्रिंग $w$ का उपभोग करने के बाद मशीन स्वीकार्य अवस्था में है।

मान्यता प्राप्त भाषा

ऑटोमेटन द्वारा मान्यता प्राप्त भाषा $L\subseteq \Sigma ^{*}$ उन सभी शब्दों का समुच्चय है जिन्हें ऑटोमेटन $L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}$ द्वारा स्वीकार किया जाता है।

पहचानने योग्य भाषाएँ

पहचानने योग्य भाषाएँ उन भाषाओं का समुच्चय होती हैं जिन्हें कुछ ऑटोमेटन द्वारा पहचाना जाता है। परिमित ऑटोमेटा के लिए पहचानने योग्य भाषाएँ नियमित भाषाएँ हैं। विभिन्न प्रकार के ऑटोमेटा के लिए, पहचानने योग्य भाषाएँ भिन्न होती हैं।

ऑटोमेटा की भिन्न परिभाषाएँ

ऑटोमेटा को गणितीय औपचारिकता के तहत उपयोगी मशीनों का अध्ययन करने के लिए परिभाषित किया गया है। तो ऑटोमेटन की परिभाषा "वास्तविक दुनिया मशीन" के अनुसार भिन्नता के लिए खुली है जिसे हम ऑटोमेटन का उपयोग करके मॉडल करना चाहते हैं। लोगों ने ऑटोमेटा की कई भिन्नताओं का अध्ययन किया है। ऑटोमेटा के विभिन्न घटकों की परिभाषा में कुछ लोकप्रिय बदलाव निम्नलिखित हैं।

इनपुट

• परिमित इनपुट- ऑटोमेटन जो प्रतीकों के केवल परिमित अनुक्रमों को स्वीकार करता है। उपरोक्त परिचयात्मक परिभाषा में केवल परिमित शब्द सम्मिलित हैं।
• अनंत इनपुट- ऑटोमेटन जो अनंत शब्द (ω-शब्द) स्वीकार करता है। ऐसे ऑटोमेटा को ω-ऑटोमेटा कहा जाता है।
• ट्री इनपुट- इनपुट प्रतीकों के क्रम के स्थान पर प्रतीकों का एक ट्री हो सकता है। इस स्थिति में प्रत्येक प्रतीक को पढ़ने के बाद, ऑटोमेटन इनपुट ट्री में सभी आनुक्रमिक प्रतीकों को पढ़ता है। ऐसा कहा जाता है कि ऑटोमेटन प्रत्येक आनुक्रमिक के लिए स्वयं की एक प्रति बनाता है और ऐसी प्रत्येक प्रतिलिपि ऑटोमेटन के संक्रमण संबंध के अनुसार अवस्था से आनुक्रमिक प्रतीकों में से एक पर रन करने लगता है। ऐसे ऑटोमेटन को ट्री ऑटोमेटन कहा जाता है।
• अनंत ट्री इनपुट- ऊपर दिए गए दो एक्सटेंशन को जोड़ा जा सकता है, इसलिए ऑटोमेटन (इन) परिमित शाखाओं के साथ ट्री संरचना को पढ़ता है। ऐसे ऑटोमेटन को अनंत ट्री ऑटोमेटन कहा जाता है।

अवस्थाएँ

• एकल अवस्था- एक अवस्था के साथ ऑटोमेटन, जिसे संयोजन परिपथ भी कहा जाता है, परिवर्तन करता है जो संयोजन तर्क को कार्यान्वित कर सकता है।
• परिमित अवस्थाएँ- ऑटोमेटन जिसमें केवल परिमित संख्या में अवस्थाएँ होती हैं।
• अनंत अवस्थाएँ- ऑटोमेटन जिसमें अवस्थाओं की सीमित संख्या या यहाँ तक कि अवस्थाओं की गणनीय संख्या नहीं हो सकती है। ऐसी मशीनों को परिमित विवरण देने के लिए विभिन्न प्रकार की संक्षेप मेमोरी का उपयोग किया जा सकता है।
• स्टैक मेमोरी- ऑटोमेटन में स्टैक के रूप में कुछ अतिरिक्त मेमोरी भी हो सकती है जिसमें प्रतीकों को धकेला और पॉप किया जा सकता है। इस तरह के ऑटोमेटन को पुशडाउन ऑटोमेटन कहा जाता है।
• क्यू मेमोरी- ऑटोमेटन में कतार के रूप में मेमोरी हो सकती है। ऐसी मशीन को कतार मशीन कहा जाता है और ट्यूरिंग-पूर्ण है।
• टेप मेमोरी- ऑटोमेटा के इनपुट और आउटपुट को प्रायः इनपुट और आउटपुट टेप के रूप में वर्णित किया जाता है। कुछ मशीनों में ट्यूरिंग मशीन, रैखिक परिबद्ध ऑटोमेटन, और लॉग-स्पेस ट्रांसड्यूसर सहित अतिरिक्त कार्यशील टेप होते हैं।

संक्रमण फलन

• निर्धारक- किसी दी गई वर्तमान अवस्था और इनपुट प्रतीक के लिए, यदि ऑटोमेटन केवल एक और केवल एक अवस्था में जा सकता है तो यह निर्धारक ऑटोमेटन है।
• गैर नियतात्मक- ऑटोमेटन, जो इनपुट प्रतीक को पढ़ने के बाद, अपने संक्रमण संबंध द्वारा लाइसेंस के रूप में कई अवस्थाओं में से किसी में भी जा सकता है। ध्यान दें कि पद संक्रमण फलन को संक्रमण संबंध द्वारा प्रतिस्थापित किया गया है- ऑटोमेटन गैर-नियतात्मक रूप से अनुमत विकल्पों में से एक में जाने का निर्णय लेता है। ऐसे ऑटोमेटा को गैर-नियतात्मक ऑटोमेटा कहा जाता है।
• प्रत्यावर्तन- यह विचार काफी हद तक ट्री ऑटोमेटा के समान है लेकिन ऑर्थोगोनल है। ऑटोमेटन अपनी कई प्रतियाँ उसी अगले पढ़े गए प्रतीक पर रन कर सकता है। ऐसे ऑटोमेटा को वैकल्पिक ऑटोमेटा कहा जाता है।

स्वीकृति स्थिति

• परिमित शब्दों की स्वीकृति- उपरोक्त अनौपचारिक परिभाषा में वर्णित के समान।
• अनंत शब्दों की स्वीकृति- ω-ऑटोमेटन की अंतिम स्थिति नहीं हो सकती, क्योंकि अनंत शब्द कभी समाप्त नहीं होते। बल्कि, रन के दौरान दौरा की गई अवस्थाओंं के अनंत अनुक्रम को देखकर शब्द की स्वीकृति तय की जाती है।
• संभाव्य स्वीकृति- ऑटोमेटन को किसी इनपुट को दृढ़ता से स्वीकार या अस्वीकार करने की आवश्यकता नहीं है। यह शून्य और एक के बीच कुछ प्रायिकता के साथ इनपुट को स्वीकार कर सकता है। उदाहरण के लिए, क्वांटम परिमित ऑटोमेटा, ज्यामितीय ऑटोमेटा और मेट्रिक ऑटोमेटा की संभाव्य स्वीकृति है।

उपरोक्त विविधताओं के विभिन्न संयोजनों से ऑटोमेटा के कई वर्ग उत्पन्न होते हैं।

ऑटोमेटा सिद्धांत एक विषय वस्तु है जो विभिन्न प्रकार के ऑटोमेटा के गुणों का अध्ययन करता है। उदाहरण के लिए, दिए गए ऑटोमेटा के बारे में निम्नलिखित प्रश्नों का अध्ययन किया जाता है।

• औपचारिक भाषाओं का कौन सा वर्ग किसी प्रकार के ऑटोमेटा द्वारा पहचाना जा सकता है? (पहचानने योग्य भाषाएं)
• क्या संघ, प्रतिच्छेदन, या औपचारिक भाषाओं के पूरक के तहत कुछ ऑटोमेटा बंद हैं? (समापन गुण)
• औपचारिक भाषाओं के वर्ग को पहचानने के संदर्भ में एक प्रकार का ऑटोमेटा कितना अभिव्यंजक है? और, उनकी सापेक्ष अभिव्यंजक शक्ति? (भाषा पदानुक्रम)

ऑटोमेटा सिद्धांत निम्न सूची के समान समस्याओं को हल करने के लिए किसी प्रभावी एल्गोरिदम के अस्तित्व या अस्तित्व का भी अध्ययन करता है-

• क्या ऑटोमेटन कम से कम एक इनपुट शब्द स्वीकार करता है? (खालीपन की जाँच)
• क्या मान्यता प्राप्त भाषा को बदले बिना किसी दिए गए गैर-नियतात्मक ऑटोमेटन को नियतात्मक ऑटोमेटन में बदलना संभव है? (निर्धारण)
• दी गई औपचारिक भाषा के लिए, इसे पहचानने वाला सबसे छोटा ऑटोमेटन कौन सा है? (न्यूनतमीकरण)

ऑटोमेटा के प्रकार

निम्नलिखित ऑटोमेटा के प्रकारों की अपूर्ण सूची है।

ऑटोमेटन	पहचानने योग्य भाषाएँ
गैर नियतात्मक/नियतात्मक परिमित अवस्था मशीन (एफएसएम)	नियमित भाषाएँ
निर्धारक पुशडाउन ऑटोमेटन (डीपीडीए)	नियतात्मक संदर्भ-मुक्त भाषाएँ
पुशडाउन ऑटोमेटन (पीडीए)	संदर्भ-मुक्त भाषाएँ
रैखिक परिबद्ध ऑटोमेटन (एलबीए)	संदर्भ-संवेदनशील भाषाएं
ट्यूरिंग मशीन	पुनरावर्ती रूप से गणनीय भाषाएँ
निर्धारक बुची ऑटोमेटन	ω-सीमा भाषाएँ
गैर नियतात्मक बुच्ची ऑटोमेटन	ω-नियमित भाषाएँ
राबिन ऑटोमेटन, स्ट्रीट ऑटोमेटन, समता ऑटोमेटन, मुलर ऑटोमेटन
भारित ऑटोमेटन

असतत, निरंतर और संकर ऑटोमेटा

प्रायः ऑटोमेटा सिद्धांत संक्षेप मशीनों की अवस्थाओं का वर्णन करता है, लेकिन असतत ऑटोमेटा, एनालॉग ऑटोमेटा या निरंतर ऑटोमेटा, या संकर असतत-निरंतर ऑटोमेटा हैं, जो क्रमशः डिजिटल डेटा, एनालॉग डेटा या निरंतर समय, या डिजिटल और एनालॉग डेटा का उपयोग करते हैं।

शक्तियों के संदर्भ में पदानुक्रम

निम्नलिखित विभिन्न प्रकार की आभासी मशीनों की शक्तियों के संदर्भ में अपूर्ण पदानुक्रम है। पदानुक्रम उन भाषाओं की नेस्टेड श्रेणियों को दर्शाता है जिन्हें मशीनें स्वीकार करने में सक्षम हैं।

ऑटोमेटन

नियतात्मक परिमित ऑटोमेटन (डीएफए) -- निम्नतम शक्ति (समान शक्ति) $||$ (समान शक्ति) गैर नियतात्मक परिमित ऑटोमेटन (एनएफए) (ऊपर कमजोर है) $\cap$ (नीचे दृढ़ है) नियतात्मक पुश डाउन ऑटोमेटन (डीपीडीए-I) 1 पुश-डाउन स्टोर के साथ $\cap$ गैर नियतात्मक पुश डाउन ऑटोमेटन (एनपीडीए-I) 1 पुश-डाउन स्टोर के साथ $\cap$ रैखिक परिबद्ध ऑटोमेटन (एलबीए) $\cap$ नियतात्मक पुश डाउन ऑटोमेटन (डीपीडीए -II) 2 पुश-डाउन स्टोर्स के साथ $||$ गैर नियतात्मक पुश डाउन ऑटोमेटन (एनपीडीए-II) 2 पुश-डाउन स्टोर्स के साथ $||$ निर्धारक ट्यूरिंग मशीन (डीटीएम) $||$ गैर नियतात्मक ट्यूरिंग मशीन (एनटीएम) $||$ संभाव्य ट्यूरिंग मशीन (पीटीएम) $||$ मल्टीटेप ट्यूरिंग मशीन (एमटीएम) $||$ बहुआयामी ट्यूरिंग मशीन

अनुप्रयोग

ऑटोमेटा सिद्धांत में प्रत्येक मॉडल कई अनुप्रयुक्त क्षेत्रों में महत्वपूर्ण भूमिका निभाता है। परिमित ऑटोमेटा का उपयोग पाठ प्रसंस्करण, संकलक और हार्डवेयर डिज़ाइन में किया जाता है। प्रसंग-मुक्त व्याकरण (CFGs) का उपयोग प्रोग्रामिंग भाषाओं और कृत्रिम बुद्धिमत्ता में किया जाता है। मूल रूप से, सीएफजी (CFGs) का उपयोग मानव भाषाओं के अध्ययन में किया जाता था। कोशिकीय ऑटोमेटा का उपयोग कृत्रिम जीवन के क्षेत्र में किया जाता है, सबसे प्रसिद्ध उदाहरण जॉन कॉनवे का गेम ऑफ लाइफ है। कुछ अन्य उदाहरण जिन्हें जीव विज्ञान में ऑटोमेटा सिद्धांत का उपयोग करके समझाया जा सकता है उनमें मोलस्क और पाइन शंकु वृद्धि और रंजकता पैटर्न सम्मिलित हैं। आगे बढ़ते हुए, एक सिद्धांत का सुझाव है कि पूरे ब्रह्मांड की गणना किसी प्रकार के असतत ऑटोमेटन द्वारा की जाती है, जिसका कुछ वैज्ञानिकों द्वारा समर्थन किया जाता है। यह विचार कोनराड ज़्यूस के काम में उत्पन्न हुआ, और एडवर्ड फ्रेडकिन द्वारा अमेरिका में लोकप्रिय किया गया। ऑटोमेटा परिमित क्षेत्रों के सिद्धांत में भी प्रकट होता है- अलघुकरणीय बहुपदों का समुच्चय जिसे डिग्री दो बहुपदों की रचना के रूप में लिखा जा सकता है, वास्तव में एक नियमित भाषा है। एक अन्य समस्या जिसके लिए ऑटोमेटा का उपयोग किया जा सकता है वह नियमित भाषाओं का समावेश है।

ऑटोमेटा अनुरूपक

ऑटोमेटा अनुरूपक शैक्षणिक उपकरण हैं जिनका उपयोग ऑटोमेटा सिद्धांत को सिखाने, सीखने और शोध करने के लिए किया जाता है। ऑटोमेटा अनुरूपक ऑटोमेटन के विवरण को इनपुट के रूप में लेता है और फिर मनमाने ढंग से इनपुट स्ट्रिंग के लिए इसके काम का अनुकरण करता है। ऑटोमेटन का विवरण कई तरीकों से दर्ज किया जा सकता है। ऑटोमेटन को एक सांकेतिक भाषा में परिभाषित किया जा सकता है या इसके विनिर्देशन को पूर्वनिर्धारित रूप में दर्ज किया जा सकता है या माउस को क्लिक करके और खींचकर इसका संक्रमण आरेख तैयार किया जा सकता है। प्रसिद्ध ऑटोमेटा अनुरूपक में ट्यूरिंग वर्ल्ड, जेएफएलएपी (JFLAP), वीएएस (VAS), टीएजीएस (TAGS) और सिमस्टूडियो सम्मिलित हैं।

श्रेणी सिद्धांत से संबंध

पिछले खंड में वर्णित विभिन्न प्रकारों में ऑटोमेटा वर्गीकरण के बाद ऑटोमेटा की कई अलग-अलग श्रेणियों को परिभाषित किया जा सकता है। नियतात्मक ऑटोमेटा, अनुक्रमिक मशीन या अनुक्रमिक ऑटोमेटा की गणितीय श्रेणी, और ऑटोमेटा समरूपता के साथ ट्यूरिंग मशीन ऑटोमेटा के बीच तीरों को परिभाषित करती है, कार्तीय बंद श्रेणी है, इसमें श्रेणीबद्ध सीमाएँ और सह-सीमाएँ दोनों हैं। ऑटोमेटा समरूपता ऑटोमेटन A_i के पंचगुना को दूसरे ऑटोमेटन A_j के पंचगुना पर मैप करता है। ऑटोमेटा समरूपता को ऑटोमेटा रूपांतरणों या अर्धसमूह समरूपता के रूप में भी माना जा सकता है, जब ऑटोमेटन के अवस्था अंतराल, S को अर्धसमूह S_g के रूप में परिभाषित किया जाता है। मोनोइडल श्रेणियों में मोनोइड्स को ऑटोमेटा के लिए उपयुक्त सेटिंग के रूप में भी माना जाता है।

परिवर्तनशील ऑटोमेटा की श्रेणियाँ

नोर्बर्ट वीनर ने अपनी पुस्तक द ह्यूमन यूज़ ऑफ़ ह्यूमन बीइंग के माध्यम से द एंडोमोर्फिज़्म $A_{i}\to A_{i}$ में परिवर्तनशील ऑटोमेटन को भी परिभाषित किया जा सकता है। तब कोई यह दिखा सकता है कि इस तरह के परिवर्तनशील ऑटोमेटा समरूपता गणितीय समूह बनाते हैं। गैर-नियतात्मक, या अन्य जटिल प्रकार के ऑटोमेटा की स्थितियों में, अंतःरूपांतरण का बाद वाला समुच्चय, हालांकि, परिवर्तनशील ऑटोमेटन ग्रुपॉइड बन सकता है। इसलिए, सबसे सामान्य स्थिति में, किसी भी प्रकार के परिवर्तनशील ऑटोमेटा की श्रेणियां ग्रुपॉयड्स या ग्रुपॉयड श्रेणियों की श्रेणियां हैं। इसके अलावा, प्रतिवर्ती ऑटोमेटा की श्रेणी तब 2-श्रेणी है, और 2-श्रेणी के ग्रुपॉयड्स या ग्रुपॉयड श्रेणी की उपश्रेणी भी है।

यह भी देखें

• बूलियन अवकल गणना

अग्रिम पठन

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Pearson Education. ISBN 978-0-201-44124-6.{{cite book}}: CS1 maint: uses authors parameter (link)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Part One: Automata and Languages, chapters 1–2, pp. 29–122. Section 4.1: Decidable Languages, pp. 152–159. Section 5.1: Undecidable Problems from Language Theory, pp. 172–183.
• Elaine Rich (2008). Automata, Computability and Complexity: Theory and Applications. Pearson. ISBN 978-0-13-228806-4.
• Salomaa, Arto (1985). Computation and automata. Encyclopedia of Mathematics and Its Applications. Vol. 25. Cambridge University Press. ISBN 978-0-521-30245-6. Zbl 0565.68046.
• Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 978-0-521-61324-8. Zbl 1127.68049.
• Conway, J.H. (1971). Regular algebra and finite machines. Chapman and Hall Mathematics Series. London: Chapman & Hall. Zbl 0231.94041.
• John M. Howie (1991) Automata and Languages, Clarendon Press ISBN 0-19-853424-8 MR1254435
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• James P. Schmeiser, David T. Barnard (1995). Producing a top-down parse order with bottom-up parsing. Elsevier North-Holland.{{cite book}}: CS1 maint: uses authors parameter (link)
• Igor Aleksander, F.Keith Hanna (1975). Automata Theory : An Engineering Approach. New York: Crane Russak. ISBN 978-0-8448-0657-0.{{cite book}}: CS1 maint: uses authors parameter (link)
• Marvin Minsky (1967). Computation : Finite and infinite machines. Princeton, N.J.: Prentice Hall.
• John C. Martin (2011). Introduction to Languages and The Theory of Computation. New York: McGraw Hill. ISBN 978-0-07-319146-1.

बाहरी संबंध

• dk.brics.automaton
• libfa