मूर मशीन: Difference between revisions

From Vigyanwiki
No edit summary
 
(6 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Short description|Finite-state machine whose output values are determined only by its current state}}
{{Short description|Finite-state machine whose output values are determined only by its current state}}
गणना के सिद्धांत में, मूर मशीन एक परिमित-राज्य मशीन है जिसका वर्तमान आउटपुट मान केवल इसकी वर्तमान स्थिति (कंप्यूटर विज्ञान) द्वारा निर्धारित किया जाता है। यह एक [[ मैली मशीन ]] के विपरीत है, जिसका आउटपुट मूल्य इसकी वर्तमान स्थिति और इसके इनपुट के मूल्यों दोनों द्वारा निर्धारित किया जाता है। अन्य [[परिमित अवस्था मशीन]]ों की तरह, मूर मशीनों में, इनपुट आमतौर पर [https://www.sciencedirect.com/topics/computer-science/moore-machine अगली अवस्था को प्रभावित करता है]। इस प्रकार इनपुट अप्रत्यक्ष रूप से बाद के आउटपुट को प्रभावित कर सकता है, लेकिन वर्तमान या तत्काल आउटपुट को नहीं। मूर मशीन का नाम एडवर्ड एफ. मूर के नाम पर रखा गया है, जिन्होंने 1956 के पेपर, "[[सोचा प्रयोग]]|गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन्स" में इस अवधारणा को प्रस्तुत किया था।<ref name="gedanken">{{cite journal| last=Moore| first=Edward F| title=अनुक्रमिक मशीनों पर विचार प्रयोग| pages=129–153| journal=Automata Studies, Annals of Mathematical Studies| issue=34| publisher=Princeton University Press| location=Princeton, N.J.| year=1956}}</ref>
गणना के सिद्धांत में, '''मूर मशीन''' एक फाईनाईट-स्टेट मशीन है जिसका करंट आउटपुट वैल्यू केवल इसकी करंट स्टेट (कंप्यूटर विज्ञान) द्वारा निर्धारित किया जाता है। यह एक [[ मैली मशीन |मैली मशीन]] के विपरीत है, जिसका आउटपुट मूल्य इसकी करंट स्टेट और इसके इनपुट के वैल्यू दोनों द्वारा निर्धारित किया जाता है। अन्य [[परिमित अवस्था मशीन|फाईनाईट स्टेट मशीन]] की तरह, मूर मशीनों में, इनपुट सामान्यतः [https://www.sciencedirect.com/topics/computer-science/moore-machine अगली स्टेट को इन्फ्लुएंस करता है]। इस टाइप इनपुट इनडायरेक्टली बाद के आउटपुट को इन्फ्लुएंस कर सकता है, लेकिन करंट या इमीडियेट आउटपुट को नहीं। मूर मशीन का नाम एडवर्ड एफ. मूर के नाम पर रखा गया है, जिन्होंने 1956 के पेपर, गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन्स" में इस कांसेप्ट को प्रस्तुत किया था। <ref name="gedanken">{{cite journal| last=Moore| first=Edward F| title=अनुक्रमिक मशीनों पर विचार प्रयोग| pages=129–153| journal=Automata Studies, Annals of Mathematical Studies| issue=34| publisher=Princeton University Press| location=Princeton, N.J.| year=1956}}</ref>




== औपचारिक परिभाषा ==
== फॉर्मल डेफिनिशन ==


मूर मशीन को एन-टुपल|6-टुपल के रूप में परिभाषित किया जा सकता है <math>(S, s_0, \Sigma, O, \delta, G)</math> निम्नलिखित से मिलकर:
मूर मशीन को निम्नलिखित से मिलकर 6-टुपल <math>(S, s_0, \Sigma, O, \delta, G)</math> के रूप में डिफाइन किया जा सकता है:
* राज्य का एक सीमित सेट (कंप्यूटर विज्ञान) <math>S</math>
* स्टेट <math>S</math> का एक फाईनाईट सेट (कंप्यूटर विज्ञान)  
* एक आरंभिक अवस्था (जिसे आरंभिक अवस्था भी कहा जाता है) <math>s_0</math> जो कि एक तत्व है <math>S</math>
* एक स्टार्ट स्टेट <math>s_0</math> (जिसे स्टार्ट स्टेट भी कहा जाता है) जो कि <math>S</math> का एक एलिमेंट है
* एक परिमित सेट जिसे इनपुट [[वर्णमाला (कंप्यूटर विज्ञान)]] कहा जाता है <math>\Sigma</math>
* एक फाईनाईट सेट जिसे इनपुट [[वर्णमाला (कंप्यूटर विज्ञान)|अल्फाबेट (कंप्यूटर विज्ञान)]] <math>\Sigma</math> कहा जाता है
* एक परिमित सेट जिसे आउटपुट वर्णमाला (कंप्यूटर विज्ञान) कहा जाता है <math>O</math>
* एक फाईनाईट सेट जिसे आउटपुट अल्फाबेट (कंप्यूटर विज्ञान) <math>O</math> कहा जाता है
* एक संक्रमण फलन (गणित) <math>\delta : S \times \Sigma \rightarrow S </math> एक राज्य और इनपुट वर्णमाला को अगले राज्य में मैप करना
* एक ट्रांजीशन फलन (गणित) <math>\delta : S \times \Sigma \rightarrow S </math> एक स्टेट और इनपुट अल्फाबेट को अगले स्टेट में मैप करना
* एक आउटपुट फ़ंक्शन <math>G : S \rightarrow O</math> प्रत्येक राज्य को आउटपुट वर्णमाला में मैप करना
* एक आउटपुट फ़ंक्शन <math>G : S \rightarrow O</math> प्रत्येक स्टेट को आउटपुट अल्फाबेट में मैप करना


मूर मशीन को एक प्रतिबंधित प्रकार के [[परिमित-अवस्था ट्रांसड्यूसर]] के रूप में माना जा सकता है।
मूर मशीन को एक रिस्ट्रिक्टेड टाइप के [[परिमित-अवस्था ट्रांसड्यूसर|फाईनाईट-स्टेट ट्रांसड्यूसर]] के रूप में माना जा सकता है।


==दृश्य प्रतिनिधित्व==
==विसुअल रिप्रजेंटेशन==


===तालिका===
===टेबल===
एक [[राज्य संक्रमण तालिका]] एक तालिका है जो संक्रमण संबंध में सभी त्रिगुणों को सूचीबद्ध करती है <math>\delta : S \times \Sigma \rightarrow S </math>.
[[राज्य संक्रमण तालिका|स्टेट ट्रांजीशन टेबल]] एक टेबल है जो ट्रांजीशन रिलेशनशिप में सभी ट्रिपल्स <math>\delta : S \times \Sigma \rightarrow S </math> को सूचीबद्ध करती है।


===आरेख===
===डायग्राम===
मूर मशीन के लिए [[राज्य आरेख]], या मूर आरेख, एक आरेख राज्य आरेख है जो प्रत्येक राज्य के साथ एक आउटपुट मान को जोड़ता है।
मूर मशीन के लिए [[राज्य आरेख|स्टेट डायग्राम]], या मूर डायग्राम, एक डायग्राम स्टेट डायग्राम है जो प्रत्येक स्टेट के साथ एक आउटपुट वैल्यू को जोड़ता है।


==मीली मशीनों से संबंध==
==मीली मशीनों से रिलेशनशिप==
चूँकि मूर और मीली मशीनें दोनों प्रकार की परिमित-राज्य मशीनें हैं, वे समान रूप से अभिव्यंजक हैं: किसी भी प्रकार का उपयोग [[नियमित भाषा]] को पार्स करने के लिए किया जा सकता है।
चूँकि मूर और मीली मशीनें दोनों टाइप की फाईनाईट-स्टेट मशीनें हैं, वे समान रूप से एक्सप्रेसिव हैं: किसी भी टाइप का उपयोग [[नियमित भाषा|रेगुलर लैंग्वेज]] को पार्स करने के लिए किया जा सकता है।


मूर मशीनों और मीली मशीनों के बीच अंतर यह है कि बाद में, एक संक्रमण का आउटपुट वर्तमान स्थिति (कंप्यूटर विज्ञान) और वर्तमान इनपुट के संयोजन से निर्धारित होता है (<math>S \times \Sigma</math> के डोमेन के रूप में <math>G</math>), वर्तमान स्थिति के विपरीत (<math>S</math> के डोमेन के रूप में <math>G</math>). जब एक राज्य आरेख के रूप में दर्शाया जाता है,
मूर मशीनों और मीली मशीनों के बीच अंतर यह है कि बाद में, एक ट्रांजीशन का आउटपुट करंट स्टेट (कंप्यूटर विज्ञान) और करंट इनपुट के कॉम्बिनेशन से निर्धारित होता है (<math>S \times \Sigma</math> के डोमेन के रूप में <math>G</math>), करंट स्टेट के विपरीत (<math>S</math> के डोमेन के रूप में <math>G</math>)। जब एक स्टेट डायग्राम के रूप में दर्शाया जाता है,
* मूर मशीन के लिए, प्रत्येक नोड (स्थिति) को आउटपुट मान के साथ लेबल किया जाता है;
* मूर मशीन के लिए, प्रत्येक नोड (स्टेट) को आउटपुट वैल्यू के साथ लेबल किया जाता है;
* मीली मशीन के लिए, प्रत्येक चाप (संक्रमण) को आउटपुट मान के साथ लेबल किया जाता है।
* मीली मशीन के लिए, प्रत्येक आर्क (ट्रांजीशन) को आउटपुट वैल्यू के साथ लेबल किया जाता है।


प्रत्येक मूर मशीन <math>M</math> समान अवस्थाओं और बदलावों और आउटपुट फ़ंक्शन वाली मीली मशीन के समतुल्य है <math>G(s, \sigma) = G_M(\delta_M(s, \sigma))</math>, जो प्रत्येक राज्य-इनपुट जोड़ी लेता है <math>(s, \sigma)</math> और पैदावार <math>G_M(\delta_M(s, \sigma))</math>, कहाँ <math>G_M</math> है <math>M</math>का आउटपुट फ़ंक्शन और <math>\delta_M</math> है <math>M</math>का संक्रमण फ़ंक्शन.
प्रत्येक मूर मशीन <math>M</math> समान स्टेट और ट्रांजीशन और आउटपुट फ़ंक्शन वाली मीली मशीन <math>G(s, \sigma) = G_M(\delta_M(s, \sigma))</math> के समतुल्य है, जो प्रत्येक स्टेट-इनपुट जोड़ी <math>(s, \sigma)</math> लेता है और <math>G_M(\delta_M(s, \sigma))</math> यील्ड करता है, जहाँ <math>G_M</math> <math>M</math> का आउटपुट फ़ंक्शन है और <math>\delta_M</math> <math>M</math> का ट्रांजीशन फ़ंक्शन है।


हालाँकि, प्रत्येक मीली मशीन को समकक्ष मूर मशीन में परिवर्तित नहीं किया जा सकता है। कुछ को केवल लगभग समकक्ष मूर मशीन में परिवर्तित किया जा सकता है, जिसमें आउटपुट समय पर स्थानांतरित हो जाते हैं। यह उस तरीके के कारण है जिसमें इनपुट/आउटपुट जोड़े बनाने के लिए राज्य लेबल को संक्रमण लेबल के साथ जोड़ा जाता है। एक परिवर्तन पर विचार करें <math>s_i\rightarrow s_j</math> राज्य से <math>s_i</math> कहना <math>s_j</math>. संक्रमण का कारण बनने वाला इनपुट <math>s_i\rightarrow s_j</math> किनारे को लेबल करता है <math>(s_i, s_j)</math>. उस इनपुट के अनुरूप आउटपुट, राज्य का लेबल है <math>s_i</math>.<ref>{{cite book|last1=Lee|first1=Edward Ashford|last2=Seshia|first2=Sanjit Arunkumar|title=एंबेडेड सिस्टम का परिचय|date=2013|publisher=Lulu.com|location=UC Berkeley|isbn=9780557708574|edition=1.08|url=http://leeseshia.org/|accessdate=1 July 2014}}</ref> ध्यान दें कि यह संक्रमण की स्रोत स्थिति है। इसलिए प्रत्येक इनपुट के लिए, आउटपुट इनपुट प्राप्त होने से पहले ही तय हो जाता है, और पूरी तरह से वर्तमान स्थिति पर निर्भर करता है। यह ई. मूर की मूल परिभाषा है। राज्य के लेबल का उपयोग करना एक सामान्य गलती है <math>s_j</math> संक्रमण के लिए आउटपुट के रूप में <math>s_i\rightarrow s_j</math>.
हालाँकि, प्रत्येक मीली मशीन को समकक्ष मूर मशीन में कन्वर्ट नहीं किया जा सकता है। कुछ को केवल लगभग समकक्ष मूर मशीन में कन्वर्ट किया जा सकता है, जिसमें आउटपुट टाइम पर शिफ्ट हो जाते हैं। यह उस तरीके के कारण है जिसमें इनपुट/आउटपुट जोड़े बनाने के लिए स्टेट लेबल को ट्रांजीशन लेबल के साथ जोड़ा जाता है। एक ट्रांजीशन पर विचार करें <math>s_i\rightarrow s_j</math> <math>s_i</math> स्टेट से <math>s_j</math> स्टेट तक। ट्रांजीशन का कारण बनने वाला इनपुट <math>s_i\rightarrow s_j</math> एज <math>(s_i, s_j)</math> को लेबल करता है। उस इनपुट के अनुरूप आउटपुट, स्टेट <math>s_i</math> का लेबल है। <ref>{{cite book|last1=Lee|first1=Edward Ashford|last2=Seshia|first2=Sanjit Arunkumar|title=एंबेडेड सिस्टम का परिचय|date=2013|publisher=Lulu.com|location=UC Berkeley|isbn=9780557708574|edition=1.08|url=http://leeseshia.org/|accessdate=1 July 2014}}</ref> ध्यान दें कि यह ट्रांजीशन की सोर्स स्टेट है। इसलिए प्रत्येक इनपुट के लिए, आउटपुट इनपुट प्राप्त होने से पहले ही फिक्स हो जाता है, और पूरी तरह से करंट स्टेट पर निर्भर करता है। यह ई. मूर की ओरिजिनल डेफिनिशन है। स्टेट के लेबल का <math>s_j</math> ट्रांजीशन के लिए आउटपुट <math>s_i\rightarrow s_j</math> के रूप में उपयोग करना एक कॉमन मिस्टेक है।


==उदाहरण==
==उदाहरण==
इनपुट/आउटपुट की संख्या के अनुसार प्रकार।
इनपुट/आउटपुट की संख्या के अकॉर्डिंग टाइप।


===सरल===
===सिंपल===


सरल मूर मशीनों में एक इनपुट और एक आउटपुट होता है:
सरल मूर मशीनों में एक इनपुट और एक आउटपुट होता है:
* [[XOR]] का उपयोग करके [[किनारे का पता लगाना]]
* [[XOR]] का उपयोग करके एज डिटेक्ट करना
* विकिपुस्तकें:फ्रैक्टल्स/गणित/समूह/बाइनरी जोड़ने वाली मशीन
* बाइनरी अड्डिंग मशीन
* क्लॉक्ड अनुक्रमिक प्रणाली#क्लॉक्ड अनुक्रमिक सिस्टम (मूर मशीन का एक प्रतिबंधित रूप जहां स्थिति केवल तभी बदलती है जब वैश्विक घड़ी सिग्नल बदलता है)
* क्लॉक्ड सीक्वेनशीअल सिस्टम (मूर मशीन का एक रिस्ट्रिक्टेड रूप जहां स्टेट केवल तभी बदलती है जब वैश्विक क्लॉक सिग्नल बदलता है)


अधिकांश डिजिटल इलेक्ट्रॉनिक सिस्टम क्लॉक्ड अनुक्रमिक सिस्टम#क्लॉक्ड अनुक्रमिक सिस्टम के रूप में डिज़ाइन किए गए हैं। क्लॉक्ड अनुक्रमिक सिस्टम मूर मशीन का एक प्रतिबंधित रूप है जहां स्थिति केवल तभी बदलती है जब वैश्विक घड़ी सिग्नल बदलता है। आमतौर पर वर्तमान स्थिति [[फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स)]]|फ्लिप-फ्लॉप में संग्रहीत होती है, और एक वैश्विक घड़ी सिग्नल फ्लिप-फ्लॉप के घड़ी इनपुट से जुड़ा होता है। क्लॉक्ड अनुक्रमिक सिस्टम इलेक्ट्रॉनिक्स समस्याओं में मेटास्टेबिलिटी को हल करने का एक तरीका है। एक विशिष्ट इलेक्ट्रॉनिक मूर मशीन में वर्तमान स्थिति को आउटपुट (लैम्ब्डा) में डिकोड करने के लिए एक [[संयोजन तर्क]] श्रृंखला शामिल होती है। जैसे ही वर्तमान स्थिति बदलती है, वे परिवर्तन उस श्रृंखला में तरंगित हो जाते हैं, और लगभग तुरंत ही आउटपुट अपडेट हो जाता है। यह सुनिश्चित करने के लिए डिज़ाइन तकनीकें हैं कि उस संक्षिप्त अवधि के दौरान आउटपुट पर कोई [[गड़बड़]]ी न हो, जबकि वे परिवर्तन श्रृंखला के माध्यम से तरंगित हो रहे हों, लेकिन अधिकांश सिस्टम डिज़ाइन किए गए हैं ताकि उस संक्षिप्त संक्रमण समय के दौरान गड़बड़ियों को नजरअंदाज कर दिया जाए या अप्रासंगिक हो जाएं। आउटपुट तब तक अनिश्चित काल तक समान रहते हैं (एलईडी उज्ज्वल रहते हैं, बिजली मोटरों से जुड़ी रहती है, [[solenoid]] सक्रिय रहते हैं, आदि), जब तक कि मूर मशीन फिर से स्थिति नहीं बदलती।
अधिकांश डिजिटल इलेक्ट्रॉनिक सिस्टम क्लॉक्ड सीक्वेनशीअल सिस्टम के रूप में डिज़ाइन किए गए हैं। क्लॉक्ड सीक्वेनशीअल सिस्टम मूर मशीन का एक रिस्ट्रिक्टेड रूप है जहां स्टेट केवल तभी बदलती है जब वैश्विक क्लॉक सिग्नल बदलता है। सामान्यतः करंट स्टेट [[फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स)]] में स्टोर होती है, और एक वैश्विक क्लॉक सिग्नल फ्लिप-फ्लॉप के क्लॉक इनपुट से जुड़ा होता है। क्लॉक्ड सीक्वेनशीअल सिस्टम इलेक्ट्रॉनिक्स प्रॉब्लम में मेटास्टेबिलिटी को हल करने का एक तरीका है। एक टिपिकल इलेक्ट्रॉनिक मूर मशीन में करंट स्टेट को आउटपुट (लैम्ब्डा) में डिकोड करने के लिए एक [[संयोजन तर्क|कॉम्बिनेशन लॉजिक]] चेन इन्क्लूड होती है। जैसे ही करंट स्टेट बदलती है, वे ट्रांजीशन उस श्रृंखला में रिप्पल हो जाते हैं, और लगभग तुरंत ही आउटपुट अपडेट हो जाता है। यह सुनिश्चित करने के लिए डिज़ाइन तकनीकें हैं कि उस ब्रीफ ट्रांजीशन टाइम के दौरान आउटपुट पर कोई [[गड़बड़|ग्लिच]] न हो, जबकि वे ट्रांजीशन श्रृंखला के माध्यम से तरंगित हो रहे हों, लेकिन अधिकांश सिस्टम डिज़ाइन किए गए हैं ताकि उस ब्रीफ ट्रांजीशन टाइम के उपरान्त ग्लिच को इग्नोर कर दिया जाए या अप्रासंगिक हो जाएं। आउटपुट तब तक इंडेफिनिटेली समान रहते हैं (एलईडी ब्राइट रहते हैं, बिजली मोटरों से जुड़ी रहती है, [[solenoid|सोलेनोइड]] एनेरजाइज़ड रहते हैं, आदि), जब तक कि मूर मशीन फिर से स्टेट नहीं बदलती।


[[File:Moore-Automat-en.svg|center|alt=alt text|संयोजन तर्क में मूर मशीन]]
[[File:Moore-Automat-en.svg|center|alt=alt text|कॉम्बिनेशन तर्क में मूर मशीन]]


====कार्य उदाहरण====
====वर्कड एक्साम्पल====
अनुक्रमिक नेटवर्क में एक इनपुट और एक आउटपुट होता है। आउटपुट 1 हो जाता है और उसके बाद 1 ही रहता है जब इनपुट के रूप में कम से कम दो 0 और दो 1 आए हों।
सीक्वेनशीअल नेटवर्क में एक इनपुट और एक आउटपुट होता है। आउटपुट 1 हो जाता है और उसके बाद 1 ही रहता है जब इनपुट के रूप में कम से कम दो 0 और दो 1 आए हों।
[[index.php?title=File:Moore_Machine.svg|alt=उदाहरण मूर मशीन|right|397x397px]]
 
उपरोक्त विवरण के लिए नौ अवस्थाओं वाली एक मूर मशीन दाईं ओर दिखाई गई है। प्रारंभिक अवस्था अवस्था A है, और अंतिम अवस्था अवस्था I है। इस उदाहरण के लिए अवस्था तालिका इस प्रकार है:
[[File:Moore Machine.svg|दाएं|alt=उदाहरण मूर मशीन|333x333px]]
 
 
 
 
उपरोक्त डिस्क्रिप्शन के लिए नौ स्टेट वाली एक मूर मशीन दाईं ओर दिखाई गई है। इनिशियल स्टेट A है, और फाइनल स्टेट I है। इस उदाहरण के लिए स्टेट टेबल इस प्रकार है:
{| class="wikitable" style="text-align: center"
{| class="wikitable" style="text-align: center"
|-
|-
! Current state !! Input !! Next state !! Output
! करंट स्टेट !! इनपुट !! नेक्स्ट स्टेट !! आउटपुट
|-
|-
| rowspan=2 | A || 0 || D || rowspan=2 | 0
| rowspan=2 | A || 0 || D || rowspan=2 | 0
Line 94: Line 99:




===जटिल===
===कॉम्प्लेक्स===
अधिक जटिल मूर मशीनों में कई इनपुट के साथ-साथ कई आउटपुट भी हो सकते हैं।
अधिक कॉम्प्लेक्स मूर मशीनों में कई इनपुट के साथ-साथ कई आउटपुट भी हो सकते हैं।


== गेडानकेन-प्रयोग ==
== गेडानकेन-प्रयोग ==


मूर के 1956 के पेपर थॉट एक्सपेरिमेंट|गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन्स में,<ref name="gedanken"/> <math>(n;m;p)</math> ऑटोमेटा (या मशीनें) <math>S</math> होने के रूप में परिभाषित किया गया है <math>n</math> राज्य, <math>m</math> इनपुट प्रतीक और <math>p</math> आउटपुट प्रतीक. की संरचना के बारे में नौ प्रमेय सिद्ध हैं <math>S</math>, और प्रयोगों के साथ <math>S</math>. बाद में,<math>S</math> मशीनों को मूर मशीनों के नाम से जाना जाने लगा।
मूर के 1956 के पेपर थॉट गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन में, <ref name="gedanken"/> <math>(n;m;p)</math> ऑटोमेटा (या मशीनें) S को N स्टेट, m इनपुट प्रतीकों और P आउटपुट प्रतीकों के रूप में परिभाषित किया गया है। <math>S</math> की संरचना के बारे में नौ प्रमेय सिद्ध हैं, और <math>S</math> के साथ एक्सपेरिमेंट बाद में, <math>S</math> मशीनों को मूर मशीनों के नाम से जाना जाने लगा।


पेपर के अंत में, अनुभाग आगे की समस्याएं में, निम्नलिखित कार्य बताया गया है:
पेपर के अंत में, अनुभाग आगे की प्रॉब्लम में, निम्नलिखित कार्य बताया गया है:
<blockquote>एक और सीधे तौर पर सामने आने वाली समस्या प्रमेय 8 और 9 में दी गई सीमाओं में सुधार है।</blockquote>
<blockquote>एक और सीधे तौर पर सामने आने वाली प्रॉब्लम प्रमेय 8 और 9 में दी गई सीमाओं में सुधार है।</blockquote>


मूर का प्रमेय 8 इस प्रकार तैयार किया गया है:
मूर का प्रमेय 8 इस टाइप तैयार किया गया है:
<blockquote>मनमाना दिया गया <math>(n;m;p)</math> मशीन <math>S</math>, जैसे कि इसकी प्रत्येक दो अवस्थाएँ एक दूसरे से भिन्न हों, तब लंबाई का एक प्रयोग मौजूद होता है <math>\tfrac{n(n-1)}{2}</math> जो की स्थिति निर्धारित करता है <math>S</math> प्रयोग के अंत में.</blockquote>
<blockquote>दिया गया आरबिटरेरी <math>(n;m;p)</math> मशीन <math>S</math>, जैसे कि इसकी प्रत्येक दो स्टेट एक दूसरे से भिन्न हों, तब लेंथ का एक एक्सपेरिमेंट <math>\tfrac{n(n-1)}{2}</math> उपस्थित होता है जो की <math>S</math> प्रयोग के अंत में स्टेट निर्धारित करता है।</blockquote>


1957 में, अनातोली अलेक्सेविच करात्सुबा|ए. ए. करात्सुबा ने निम्नलिखित दो प्रमेयों को सिद्ध किया, जिससे उनके प्रमेय 8 की प्रयोग लंबाई की सीमा में सुधार पर मूर की समस्या पूरी तरह से हल हो गई।
1957 में, अनातोली अलेक्सेविच करात्सुबा|ए. ए. करात्सुबा ने निम्नलिखित दो थ्योरम को प्रूव किया, जिससे उनके प्रमेय 8 की एक्सपेरिमेंट लेंथ के बाउंड में सुधार पर मूर की प्रॉब्लम पूरी तरह से हल हो गई।<blockquote>'''थ्योरम A'''. यदि <math>S</math> एक <math>(n;m;p)</math> मशीन, इस टाइप कि उसकी प्रत्येक दो स्टेट एक-दूसरे से भिन्न होती हैं, तो अधिकतम लेंथ का एक ब्रान्च्ड एक्सपेरिमेंट <math>\tfrac{(n-1)(n-2)}{2} + 1</math> उपस्थित होता है जिसके माध्यम से  प्रयोग के अंत में कोई भी  <math>S</math> की स्टेट का निर्धारण कर सकता है।</blockquote><blockquote>'''थ्योरम B'''. वहाँ एक <math>(n;m;p)</math> मशीन उपस्थित है, प्रत्येक दो स्टेट एक दूसरे से भिन्न होती हैं, जैसे कि प्रयोग के अंत में मशीन की स्टेट स्थापित करने वाले सबसे छोटे एक्सपेरिमेंट <math>\tfrac{(n-1)(n-2)}{2} + 1</math> की लेंथ  बराबर होती है।</blockquote>प्रमेय ए और बी का उपयोग ऑटोमेटा थ्योरी की एक प्रॉब्लम पर चौथे वर्ष के छात्र ए.ए. करात्सुबा के कोर्स वर्क के आधार पर किया गया था, जिसे 1958 में [[मॉस्को स्टेट यूनिवर्सिटी]] के मैकेनिक्स और मैथमेटिक्स के छात्र कार्यों की कॉम्पीटीशन में टेस्टीमोनियल रिफरेन्स द्वारा प्रतिष्ठित किया गया था। करात्सुबा का पेपर 17 दिसंबर 1958 को उसपेखी मैट नौक पत्रिका को दिया गया था और जून 1960 में वहां पब्लिश हुआ। <ref>{{cite journal| last=Karatsuba| first=A. A.| title=परिमित ऑटोमेटा के सिद्धांत से एक समस्या का समाधान| pages=157–159| journal=Uspekhi Mat. Nauk| issue=15:3| year=1960}}</ref>


<ब्लॉककोट>प्रमेय ए. यदि <math>S</math> एक <math>(n;m;p)</math> मशीन, इस प्रकार कि उसकी प्रत्येक दो अवस्थाएँ एक-दूसरे से भिन्न होती हैं, तो अधिकतम लंबाई का एक शाखित प्रयोग मौजूद होता है <math>\tfrac{(n-1)(n-2)}{2} + 1</math> जिसके माध्यम से कोई भी व्यक्ति की स्थिति का निर्धारण कर सकता है <math>S</math> प्रयोग के अंत में.
प्रेजेंट डे (2011) तक, एक्सपेरिमेंट की लेंथ पर करात्सुबा का परिणाम एकमात्र सटीक नॉनलीनिअर रिजल्ट है, ऑटोमेटा सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी]] की समान प्रॉब्लम में है।
 
<ब्लॉककोट>प्रमेय बी. वहाँ एक मौजूद है <math>(n;m;p)</math> मशीन, प्रत्येक दो अवस्थाएँ एक दूसरे से भिन्न होती हैं, जैसे कि प्रयोग के अंत में मशीन की स्थिति स्थापित करने वाले सबसे छोटे प्रयोग की लंबाई बराबर होती है <math>\tfrac{(n-1)(n-2)}{2} + 1</math>.
 
प्रमेय ए और बी का उपयोग ऑटोमेटा सिद्धांत की एक समस्या पर चौथे वर्ष के छात्र ए.ए. करात्सुबा के पाठ्यक्रम कार्य के आधार पर किया गया था, जिसे 1958 में [[मॉस्को स्टेट यूनिवर्सिटी]] के यांत्रिकी और गणित संकाय के छात्र कार्यों की प्रतियोगिता में प्रशंसापत्र संदर्भ द्वारा प्रतिष्ठित किया गया था। करात्सुबा का पेपर उसपेखी मैट पत्रिका को दिया गया था। नौक 17 दिसंबर 1958 को और जून 1960 में वहां प्रकाशित हुआ।<ref>{{cite journal| last=Karatsuba| first=A. A.| title=परिमित ऑटोमेटा के सिद्धांत से एक समस्या का समाधान| pages=157–159| journal=Uspekhi Mat. Nauk| issue=15:3| year=1960}}</ref>
वर्तमान दिन (2011) तक, प्रयोगों की लंबाई पर करात्सुबा का परिणाम एकमात्र सटीक गैर-रेखीय परिणाम है, ऑटोमेटा सिद्धांत और [[कम्प्यूटेशनल जटिलता सिद्धांत]] की समान समस्याओं में।


== यह भी देखें ==
== यह भी देखें ==
* [[सिंक्रोनस सर्किट]]
* [[सिंक्रोनस सर्किट]]
* मैली मशीन
* मैली मशीन
* [[एल्गोरिथम राज्य मशीन]]
* [[एल्गोरिथम राज्य मशीन|एल्गोरिथम स्टेट मशीन]]
* [[स्वायत्त प्रणाली (गणित)]]
* [[स्वायत्त प्रणाली (गणित)]]


Line 136: Line 136:




== बाहरी संबंध ==
== बाहरी रिलेशनशिप ==
*{{Commonscatinline}}
*{{Commonscatinline}}
[[Category: स्वचालित रूप से समाप्त हो गया]]


[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:स्वचालित रूप से समाप्त हो गया]]

Latest revision as of 09:40, 22 August 2023

गणना के सिद्धांत में, मूर मशीन एक फाईनाईट-स्टेट मशीन है जिसका करंट आउटपुट वैल्यू केवल इसकी करंट स्टेट (कंप्यूटर विज्ञान) द्वारा निर्धारित किया जाता है। यह एक मैली मशीन के विपरीत है, जिसका आउटपुट मूल्य इसकी करंट स्टेट और इसके इनपुट के वैल्यू दोनों द्वारा निर्धारित किया जाता है। अन्य फाईनाईट स्टेट मशीन की तरह, मूर मशीनों में, इनपुट सामान्यतः अगली स्टेट को इन्फ्लुएंस करता है। इस टाइप इनपुट इनडायरेक्टली बाद के आउटपुट को इन्फ्लुएंस कर सकता है, लेकिन करंट या इमीडियेट आउटपुट को नहीं। मूर मशीन का नाम एडवर्ड एफ. मूर के नाम पर रखा गया है, जिन्होंने 1956 के पेपर, गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन्स" में इस कांसेप्ट को प्रस्तुत किया था। [1]


फॉर्मल डेफिनिशन

मूर मशीन को निम्नलिखित से मिलकर 6-टुपल के रूप में डिफाइन किया जा सकता है:

  • स्टेट का एक फाईनाईट सेट (कंप्यूटर विज्ञान)
  • एक स्टार्ट स्टेट (जिसे स्टार्ट स्टेट भी कहा जाता है) जो कि का एक एलिमेंट है
  • एक फाईनाईट सेट जिसे इनपुट अल्फाबेट (कंप्यूटर विज्ञान) कहा जाता है
  • एक फाईनाईट सेट जिसे आउटपुट अल्फाबेट (कंप्यूटर विज्ञान) कहा जाता है
  • एक ट्रांजीशन फलन (गणित) एक स्टेट और इनपुट अल्फाबेट को अगले स्टेट में मैप करना
  • एक आउटपुट फ़ंक्शन प्रत्येक स्टेट को आउटपुट अल्फाबेट में मैप करना

मूर मशीन को एक रिस्ट्रिक्टेड टाइप के फाईनाईट-स्टेट ट्रांसड्यूसर के रूप में माना जा सकता है।

विसुअल रिप्रजेंटेशन

टेबल

स्टेट ट्रांजीशन टेबल एक टेबल है जो ट्रांजीशन रिलेशनशिप में सभी ट्रिपल्स को सूचीबद्ध करती है।

डायग्राम

मूर मशीन के लिए स्टेट डायग्राम, या मूर डायग्राम, एक डायग्राम स्टेट डायग्राम है जो प्रत्येक स्टेट के साथ एक आउटपुट वैल्यू को जोड़ता है।

मीली मशीनों से रिलेशनशिप

चूँकि मूर और मीली मशीनें दोनों टाइप की फाईनाईट-स्टेट मशीनें हैं, वे समान रूप से एक्सप्रेसिव हैं: किसी भी टाइप का उपयोग रेगुलर लैंग्वेज को पार्स करने के लिए किया जा सकता है।

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

  • मूर मशीन के लिए, प्रत्येक नोड (स्टेट) को आउटपुट वैल्यू के साथ लेबल किया जाता है;
  • मीली मशीन के लिए, प्रत्येक आर्क (ट्रांजीशन) को आउटपुट वैल्यू के साथ लेबल किया जाता है।

प्रत्येक मूर मशीन समान स्टेट और ट्रांजीशन और आउटपुट फ़ंक्शन वाली मीली मशीन के समतुल्य है, जो प्रत्येक स्टेट-इनपुट जोड़ी लेता है और यील्ड करता है, जहाँ का आउटपुट फ़ंक्शन है और का ट्रांजीशन फ़ंक्शन है।

हालाँकि, प्रत्येक मीली मशीन को समकक्ष मूर मशीन में कन्वर्ट नहीं किया जा सकता है। कुछ को केवल लगभग समकक्ष मूर मशीन में कन्वर्ट किया जा सकता है, जिसमें आउटपुट टाइम पर शिफ्ट हो जाते हैं। यह उस तरीके के कारण है जिसमें इनपुट/आउटपुट जोड़े बनाने के लिए स्टेट लेबल को ट्रांजीशन लेबल के साथ जोड़ा जाता है। एक ट्रांजीशन पर विचार करें स्टेट से स्टेट तक। ट्रांजीशन का कारण बनने वाला इनपुट एज को लेबल करता है। उस इनपुट के अनुरूप आउटपुट, स्टेट का लेबल है। [2] ध्यान दें कि यह ट्रांजीशन की सोर्स स्टेट है। इसलिए प्रत्येक इनपुट के लिए, आउटपुट इनपुट प्राप्त होने से पहले ही फिक्स हो जाता है, और पूरी तरह से करंट स्टेट पर निर्भर करता है। यह ई. मूर की ओरिजिनल डेफिनिशन है। स्टेट के लेबल का ट्रांजीशन के लिए आउटपुट के रूप में उपयोग करना एक कॉमन मिस्टेक है।

उदाहरण

इनपुट/आउटपुट की संख्या के अकॉर्डिंग टाइप।

सिंपल

सरल मूर मशीनों में एक इनपुट और एक आउटपुट होता है:

  • XOR का उपयोग करके एज डिटेक्ट करना
  • बाइनरी अड्डिंग मशीन
  • क्लॉक्ड सीक्वेनशीअल सिस्टम (मूर मशीन का एक रिस्ट्रिक्टेड रूप जहां स्टेट केवल तभी बदलती है जब वैश्विक क्लॉक सिग्नल बदलता है)

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

alt text

वर्कड एक्साम्पल

सीक्वेनशीअल नेटवर्क में एक इनपुट और एक आउटपुट होता है। आउटपुट 1 हो जाता है और उसके बाद 1 ही रहता है जब इनपुट के रूप में कम से कम दो 0 और दो 1 आए हों।

उदाहरण मूर मशीन



उपरोक्त डिस्क्रिप्शन के लिए नौ स्टेट वाली एक मूर मशीन दाईं ओर दिखाई गई है। इनिशियल स्टेट A है, और फाइनल स्टेट I है। इस उदाहरण के लिए स्टेट टेबल इस प्रकार है:

करंट स्टेट इनपुट नेक्स्ट स्टेट आउटपुट
A 0 D 0
1 B
B 0 E 0
1 C
C 0 F 0
1 C
D 0 G 0
1 E
E 0 H 0
1 F
F 0 I 0
1 F
G 0 G 0
1 H
H 0 H 0
1 I
I 0 I 1
1 I


कॉम्प्लेक्स

अधिक कॉम्प्लेक्स मूर मशीनों में कई इनपुट के साथ-साथ कई आउटपुट भी हो सकते हैं।

गेडानकेन-प्रयोग

मूर के 1956 के पेपर थॉट गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन में, [1] ऑटोमेटा (या मशीनें) S को N स्टेट, m इनपुट प्रतीकों और P आउटपुट प्रतीकों के रूप में परिभाषित किया गया है। की संरचना के बारे में नौ प्रमेय सिद्ध हैं, और के साथ एक्सपेरिमेंट बाद में, मशीनों को मूर मशीनों के नाम से जाना जाने लगा।

पेपर के अंत में, अनुभाग आगे की प्रॉब्लम में, निम्नलिखित कार्य बताया गया है:

एक और सीधे तौर पर सामने आने वाली प्रॉब्लम प्रमेय 8 और 9 में दी गई सीमाओं में सुधार है।

मूर का प्रमेय 8 इस टाइप तैयार किया गया है:

दिया गया आरबिटरेरी मशीन , जैसे कि इसकी प्रत्येक दो स्टेट एक दूसरे से भिन्न हों, तब लेंथ का एक एक्सपेरिमेंट उपस्थित होता है जो की प्रयोग के अंत में स्टेट निर्धारित करता है।

1957 में, अनातोली अलेक्सेविच करात्सुबा|ए. ए. करात्सुबा ने निम्नलिखित दो थ्योरम को प्रूव किया, जिससे उनके प्रमेय 8 की एक्सपेरिमेंट लेंथ के बाउंड में सुधार पर मूर की प्रॉब्लम पूरी तरह से हल हो गई।

थ्योरम A. यदि एक मशीन, इस टाइप कि उसकी प्रत्येक दो स्टेट एक-दूसरे से भिन्न होती हैं, तो अधिकतम लेंथ का एक ब्रान्च्ड एक्सपेरिमेंट उपस्थित होता है जिसके माध्यम से प्रयोग के अंत में कोई भी की स्टेट का निर्धारण कर सकता है।

थ्योरम B. वहाँ एक मशीन उपस्थित है, प्रत्येक दो स्टेट एक दूसरे से भिन्न होती हैं, जैसे कि प्रयोग के अंत में मशीन की स्टेट स्थापित करने वाले सबसे छोटे एक्सपेरिमेंट की लेंथ बराबर होती है।

प्रमेय ए और बी का उपयोग ऑटोमेटा थ्योरी की एक प्रॉब्लम पर चौथे वर्ष के छात्र ए.ए. करात्सुबा के कोर्स वर्क के आधार पर किया गया था, जिसे 1958 में मॉस्को स्टेट यूनिवर्सिटी के मैकेनिक्स और मैथमेटिक्स के छात्र कार्यों की कॉम्पीटीशन में टेस्टीमोनियल रिफरेन्स द्वारा प्रतिष्ठित किया गया था। करात्सुबा का पेपर 17 दिसंबर 1958 को उसपेखी मैट नौक पत्रिका को दिया गया था और जून 1960 में वहां पब्लिश हुआ। [3]

प्रेजेंट डे (2011) तक, एक्सपेरिमेंट की लेंथ पर करात्सुबा का परिणाम एकमात्र सटीक नॉनलीनिअर रिजल्ट है, ऑटोमेटा सिद्धांत और कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी की समान प्रॉब्लम में है।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Moore, Edward F (1956). "अनुक्रमिक मशीनों पर विचार प्रयोग". Automata Studies, Annals of Mathematical Studies. Princeton, N.J.: Princeton University Press (34): 129–153.
  2. ↑ Lee, Edward Ashford; Seshia, Sanjit Arunkumar (2013). एंबेडेड सिस्टम का परिचय (1.08 ed.). UC Berkeley: Lulu.com. ISBN 9780557708574. Retrieved 1 July 2014.
  3. ↑ Karatsuba, A. A. (1960). "परिमित ऑटोमेटा के सिद्धांत से एक समस्या का समाधान". Uspekhi Mat. Nauk (15:3): 157–159.


अग्रिम पठन

  • Conway, J.H. (1971). Regular algebra and finite machines. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041.
  • Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956).
  • Karatsuba A. A. Solution of one problem from the theory of finite automata. Usp. Mat. Nauk, 15:3, 157–159 (1960).
  • Karatsuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
  • Karatsuba A. A. List of research works.

Moore-and-Mealy-Machine


बाहरी रिलेशनशिप

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=मूर_मशीन&oldid=252080’