ऑटोमेटा सिद्धांत
ऑटोमेटा सिद्धांत- असतत गणित का एक खंड जो अमूर्त ऑटोमेटा का अध्ययन करता है - गणितीय मॉडल के रूप में प्रस्तुत कंप्यूटर - और वे कार्य जिन्हें वे हल कर सकते हैं।

ऑटोमेटा का सिद्धांत एल्गोरिदम के सिद्धांत से सबसे अधिक निकटता से संबंधित है: ऑटोमेटन असतत जानकारी को चरणों में समय के असतत क्षणों में परिवर्तित करता है और किसी दिए गए एल्गोरिथम के चरणों में परिणाम उत्पन्न करता है।

• 1 शब्दावली
• 2 आवेदन
  • 2.1 विशिष्ट कार्य
• 3 यह भी देखें
• 4 साहित्य
• 5 कड़ियाँ

शब्दावली

प्रतीक- डेटा का कोई भी परमाणु ब्लॉक जो मशीन पर प्रभाव डाल सकता है। अक्सर, एक प्रतीक एक आम भाषा में एक अक्षर होता है, लेकिन यह, उदाहरण के लिए, आरेख का एक ग्राफिक तत्व हो सकता है।

• शब्द- संयोजन (कनेक्शन) के माध्यम से बनाए गए वर्णों की एक स्ट्रिंग।
• वर्णमाला- विभिन्न पात्रों का एक सीमित सेट (कई वर्ण)
• भाषा- दिए गए वर्णमाला के प्रतीकों द्वारा गठित शब्दों का समूह। परिमित या अनंत हो सकता है।

ऑटोमेटा

ऑटोमेटा नियतात्मक या गैर-नियतात्मक हो सकता है।

नियतात्मक परिमित ऑटोमेटन (डीएफए)

• एक संक्रमण कार्य है जैसे कि
• - पहली स्थिति

नॉनडेटर्मिनिस्टिक परिमित ऑटोमेटन (एनएफए)- पाँच तत्वों का एक क्रम (टपल), जहाँ:

• - automaton राज्यों का सेट
• - उस भाषा की वर्णमाला जिसे ऑटोमेटन समझता है
• संक्रमण संबंध है, जहां एक खाली शब्द है। यही है, एनएफए एक खाली शब्द के माध्यम से डीएफए के विपरीत राज्य क्यू से राज्य पी तक कूद सकता है, और क्यू से कई राज्यों में भी जा सकता है (जो फिर से डीएफए में असंभव है)
• - प्रारंभिक अवस्थाओं का सेट
• - अंतिम राज्यों का सेट।

Automaton शब्द a1,a2,…., an वर्णों की एक परिमित स्ट्रिंग को पढ़ता है, जहां ai , जिसे इनपुट शब्द कहा जाता है। सभी शब्दों के सेट को Σ* के रूप में लिखा जाता है। प्राप्त शब्द एक शब्द w * automaton द्वारा स्वीकार किया जाता है यदि qn F.

एक भाषा एल को ऑटोमेटन एम द्वारा पढ़ा (स्वीकृत) कहा जाता है यदि इसमें वर्णमाला के आधार पर डब्ल्यू शब्द होते हैं जैसे कि यदि इन शब्दों को एम में दर्ज किया जाता है, तो प्रसंस्करण के अंत में यह स्वीकार करने वाले राज्यों में से एक में आता है:

आम तौर पर, इनपुट से एक वर्ण पढ़ते समय, एक संक्रमण फ़ंक्शन का उपयोग करके राज्य से राज्य में automaton संक्रमण। ऑटोमेटा हैं जो एक चरित्र को पढ़े बिना एक नए राज्य में संक्रमण कर सकते हैं। किसी वर्ण को पढ़े बिना संक्रमण फ़ंक्शन को -jump (epsilon-jump) कहा जाता है।

आवेदन

ऑटोमेटा का सिद्धांत सभी डिजिटल तकनीकों और सॉफ्टवेयर को रेखांकित करता है, उदाहरण के लिए, एक कंप्यूटर एक परिमित राज्य मशीन के व्यावहारिक कार्यान्वयन का एक विशेष मामला है।

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

ऑटोमेटा सिद्धांत का एक अन्य महत्वपूर्ण अनुप्रयोग है गणितीय रूप से समस्याओं की सॉल्वैबिलिटी और जटिलता का कठोर निर्धारण।

विशिष्ट कार्य

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

यह सभी देखें

• पंप लेम्मा
• सार automaton
• खेल "जीवन"
• automaton का न्यूनतम रूप
• शैनन-लुपानोव प्रमेय

साहित्य

• जॉन हॉपक्रॉफ्ट, राजीव मोटवानी, जेफरी उलमैन। ऑटोमेटा थ्योरी, भाषाएं और संगणना का परिचय। - एम.: विलियम्स, 2002. - एस. 528. - आईएसबीएन 0-201-44124-1।
• औपचारिक भाषाओं, ऑटोमेटा और कम्प्यूटेशनल जटिलता के सिद्धांत पर कास्यानोव वीएन व्याख्यान। - नोवोसिबिर्स्क: एनएसयू, 1995. - सी। 112।

लिंक

• ऑटोमेटा सिद्धांत का अनुप्रयोग

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

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

सवाल "स्वचालित" की ऐसी अवधारणा के विकास के बारे में है, जिसमें अधिकतम होगा। व्यापकता की डिग्री और, एक ही समय में, पर्याप्त रूप से सार्थक समस्याओं को स्थापित करने और हल करने के लिए एक आधार के रूप में काम कर सकती है, जिसे अभी तक पूरी तरह से हल नहीं किया जा सकता है। हालाँकि, इसे के रूप में माना जा सकता है विशेष मामलानियंत्रण प्रणाली की सामान्य अवधारणा।

शब्द "ए। टी।" 20वीं शताब्दी के 50 के दशक में उपयोग में आया, हालांकि संबंधित समस्याओं ने काफी हद तक एल्गोरिदम के सिद्धांत और रिले उपकरणों के सिद्धांत के ढांचे में 30 के दशक में वापस आकार लेना शुरू कर दिया। तब भी, सिद्धांत के एल्गोरिदम पर्याप्त रूप से तैयार किए गए थे सामान्य अवधारणाएंसंगणना। automaton (ट्यूरिंग मशीन देखें) और (निहित रूप से) एक परिमित automaton (ट्यूरिंग मशीन हेड) की अवधारणा। यह पाया गया कि करने के लिए

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

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

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

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

मशीनों के प्रकार। ऑटोमेटा और सह-सम्मान का वर्गीकरण सबसे आम है। ए। टी। के खंड, विभिन्न के लिए समर्पित

निम्नलिखित विशेषताओं के अनुसार मशीनों के प्रकार।

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

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

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

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

अन्य वैज्ञानिक क्षेत्रों के साथ संबंध।

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

परिमित ऑटोमेटा के सिद्धांत और कंप्यूटर डिजाइन और प्रोग्रामिंग सिद्धांत के सिद्धांत (वी। एम। ग्लुशकोव, ए। ए। लेटिचेव्स्की) के बीच एक संबंध भी था।

लिट।: गैवरिलोव एम ए। रिले-संपर्क सर्किट का सिद्धांत। एम। - एल।, 1950 [ग्रंथ। से। 298-299]; "गणितीय संस्थान की कार्यवाही। वी.ए. स्टेकलोव एकेडमी ऑफ साइंसेज ऑफ यूएसएसआर, 1958, वी। 51; डिजिटल ऑटोमेटा का ग्लुशकोव वी.एम. संश्लेषण। एम।, 1962 [ग्रंथ। से। 464-469]; Kobrinsky N. E., Trakhtenbrot B. A. परिमित ऑटोमेटा के सिद्धांत का परिचय। एम।, 1962 [ग्रंथ। से। 399-402]; ऑटोमेटा के सिद्धांत और जैविक प्रणालियों के मॉडलिंग पर Tsetlin ML अनुसंधान। एम।, 1969 [ग्रंथ। से। 306-316]; Trakhtenbrot B. A., Barzdin Ya. M. परिमित ऑटोमेटा (व्यवहार और संश्लेषण)। एम।, 1970 [ग्रंथ सूची। से। 389-395]; ऑटोमेटा। प्रति. अंग्रेज़ी से। एम।, 1956। बी। ए, ट्रेखटेनब्रोट।

व्याटका स्टेट यूनिवर्सिटी

ऑटोमेटिक्स और कंप्यूटिंग इंजीनियरिंग के संकाय

इलेक्ट्रॉनिक कंप्यूटर विभाग

ऑटोमेटा थ्योरी (भाग I) व्याख्यान नोट्स

ऑटोमेटा सिद्धांत (भाग I)। व्याख्यान नोट्स /किरोव, व्यात्स्की राज्य विश्वविद्यालय, 2010, 56 एस।

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

व्याख्यान का पाठ्यक्रम विशेषता 230101 के पूर्णकालिक छात्रों के लिए है - "कंप्यूटर, कॉम्प्लेक्स, सिस्टम और नेटवर्क", साथ ही दिशा के स्नातक 230100.62 - "कंप्यूटर विज्ञान और कंप्यूटर प्रौद्योगिकी"।

द्वारा संकलित: पीएच.डी., विभाग के एसोसिएट प्रोफेसर। कंप्यूटर वी.यू. मेल्टसोव।

व्याटका स्टेट यूनिवर्सिटी, 2010

मेल्टसोव वी.यू.

1. परिचय 4

2. विश्लेषण और संश्लेषण की समस्याएं 4

3. सार नियंत्रण automaton 7

4. अमूर्त ऑटोमेटा का संश्लेषण 9

5. तुल्यकालिक मशीन 10

6. अतुल्यकालिक मशीनें 11

7. मीली और मूर मशीनें 12

8. ऑटोमेटा 14 . सेट करने के तरीके

8.1 ऑटोमेटा 15 . निर्दिष्ट करने का सारणीबद्ध तरीका

8.2. कॉलम 17 . का उपयोग करके ऑटोमेटन सेट करना

8.3. ऑटोमेटा 19 . निर्दिष्ट करने की मैट्रिक्स विधि

9. मीली मशीन से मूर मशीन में संक्रमण और इसके विपरीत 19

10. ऑटोमेटा संश्लेषण के चरण 23

11. एक automaton 26 . के आंतरिक राज्यों की संख्या को कम करना

12. पूरी तरह से परिभाषित ऑटोमेटा का न्यूनतमकरण। 27

13. संयुक्त automaton मॉडल (C-automaton) 31

14. automaton 32 . का संरचनात्मक संश्लेषण

14.1. एक automaton 32 . के संरचनात्मक संश्लेषण की विहित विधि

14.2 सी-ऑटोमेटन 35 . का संरचनात्मक संश्लेषण

15. automaton राज्यों की कोडिंग 41

15.1. ऑटोमेटन राज्यों की एंटी-रेसिंग कोडिंग की विधि 42

15.2. ऑटोमेटन राज्यों की नेबर कोडिंग 45

15.3. एक संयोजन सर्किट को कम करने के लिए ऑटोमेटन राज्यों को कोड करना 47

16. प्राथमिक मेमोरी ऑटोमेटा 50

17. पीएलएम और रोम 54 . पर ऑटोमेटा का संश्लेषण

1। परिचय

हाल के वर्षों में, सूचना प्रसंस्करण के लिए विभिन्न स्वचालित प्रणालियों के निर्माण और अनुप्रयोग पर अनुसंधान और कार्य बड़ी तीव्रता के साथ किया गया है। ऐसी प्रणालियाँ आमतौर पर ब्लॉक के रूप में लागू की जाती हैं जो सूचना के प्रबंधन और प्रसंस्करण के लिए एक प्रणाली बनाती हैं। इसके अनुरूप एक नए वैज्ञानिक अनुशासन का उदय हुआ, जिसे "सिस्टम थ्योरी" कहा गया।

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

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