मैली मशीन: Difference between revisions

From Vigyanwiki
No edit summary
(TEXT)
Line 24: Line 24:
#* मेयली मशीनों में, इनपुट चेंज के कारण लॉजिक होते ही आउटपुट में बदलाव हो सकता है - जब दो मशीनें आपस में जुड़ी होती हैं तो एक बड़ी समस्या होती है - यदि कोई सावधान नहीं है तो एसिंक्रोनस फीडबैक हो सकता है।
#* मेयली मशीनों में, इनपुट चेंज के कारण लॉजिक होते ही आउटपुट में बदलाव हो सकता है - जब दो मशीनें आपस में जुड़ी होती हैं तो एक बड़ी समस्या होती है - यदि कोई सावधान नहीं है तो एसिंक्रोनस फीडबैक हो सकता है।
# मीली मशीनें इनपुट पर तेजी से प्रतिक्रिया करती हैं:
# मीली मशीनें इनपुट पर तेजी से प्रतिक्रिया करती हैं:
#* एक ही चक्र में प्रतिक्रिया करें—उन्हें घड़ी का इंतज़ार करने की ज़रूरत नहीं है।
#* एक ही साईकल में रियेक्ट करें—उन्हें क्लॉक का इंतज़ार करने की आवश्यकता नहीं है।
#* मूर मशीनों में, स्थिति को आउटपुट में डिकोड करने के लिए अधिक लॉजिक की आवश्यकता हो सकती है - क्लॉक एज के बाद अधिक गेट विलंब।
#* मूर मशीनों में, स्टेट को आउटपुट में डिकोड करने के लिए अधिक लॉजिक की आवश्यकता हो सकती है - क्लॉक एज के बाद अधिक गेट डिले।


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


जब इनपुट और आउटपुट अल्फाबेट दोनों हों {{math|Σ}}, कोई माइली ऑटोमेटा से हेलिक्स [[निर्देशित ग्राफ]] भी जोड़ सकता है {{math|(''S'' × Σ, (''x'', ''i'') → (''T''(''x'', ''i''), ''G''(''x'', ''i'')))}}.<ref>Akhavi et al (2012)</ref> इस ग्राफ़ में शीर्षों के रूप में स्टेट और अक्षरों के पेअर हैं, प्रत्येक नोड आउट-डिग्री एक का है, और का उत्तराधिकारी है {{math|(''x'', ''i'')}} ऑटोमेटा की अगली स्थिति है और वह अक्षर है जो ऑटोमेटा आउटपुट होता है जब यह स्थापित होता है {{math|''x''}} और यह पत्र पढ़ता है {{math|''i''}}. यदि ऑटोमेटन द्विप्रतिवर्ती है तो यह ग्राफ असंयुक्त चक्रों का एक संघ है{{definition needed|date=September 2018}}.
जब इनपुट और आउटपुट अल्फाबेट दोनों {{math|Σ}} हों, कोई माइली ऑटोमेटा से हेलिक्स [[निर्देशित ग्राफ|डिरेक्टेड ग्राफ]] {{math|(''S'' × Σ, (''x'', ''i'') → (''T''(''x'', ''i''), ''G''(''x'', ''i'')))}} भी जोड़ सकता है। <ref>Akhavi et al (2012)</ref> इस ग्राफ़ में वेर्टिसेस के रूप में स्टेट और लेटर के पेअर हैं, प्रत्येक नोड आउट-डिग्री एक का है, और {{math|(''x'', ''i'')}} का सक्सेसर ऑटोमेटा की अगली स्टेट है और वह लेटर जो ऑटोमेटा आउटपुट होता है जब यह x में होता है और यह लेटर i पढ़ता है। यदि ऑटोमेटन बिरेवेर्सिबले है तो यह ग्राफ डिसजोइन्ट साइकल्स का एक यूनियन है।


==उदाहरण==
==उदाहरण==


===सरल ===
===सिंपल ===
[[File:Mealy.png|thumb|169px|एक इनपुट और एक आउटपुट वाली एक साधारण मीली मशीन का आरेख बताएं। (प्रत्येक इनपुट मान के लिए आउटपुट 1, यदि वर्तमान इनपुट मान पिछले से भिन्न है, या अन्यथा 0।)]]एक साधारण मीली मशीन में एक इनपुट और एक आउटपुट होता है। प्रत्येक ट्रांजीशन किनारे को इनपुट के मूल्य (लाल रंग में दिखाया गया है) और आउटपुट के मूल्य (नीले रंग में दिखाया गया है) के साथ लेबल किया गया है। मशीन स्टेट में शुरू होती है {{math|''S''<sub>i</sub>}}. (इस उदाहरण में, आउटपुट दो सबसे हाल के इनपुट मानों का अनन्य या | अनन्य-या है; इस प्रकार, मशीन एक एज डिटेक्टर लागू करती है, हर बार इनपुट फ्लिप होने पर 1 और अन्यथा 0 आउटपुट करती है।)
[[File:Mealy.png|thumb|169px|एक इनपुट और एक आउटपुट वाली एक साधारण मीली मशीन का डायग्राम बताएं। (प्रत्येक इनपुट वैल्यू के लिए आउटपुट 1, यदि वर्तमान इनपुट वैल्यू पिछले से भिन्न है, या अन्यथा 0।)]]एक साधारण मीली मशीन में एक इनपुट और एक आउटपुट होता है। प्रत्येक ट्रांजीशन एज को इनपुट के वैल्यू (लाल रंग में दिखाया गया है) और आउटपुट के वैल्यू (नीले रंग में दिखाया गया है) के साथ लेबल किया गया है। मशीन स्टेट {{math|''S''<sub>i</sub>}} में प्रारम्भ होती है। (इस उदाहरण में, आउटपुट दो सबसे हाल के इनपुट वैल्यू का एक्सक्लूसिव-और है; इस प्रकार, मशीन एक एज डिटेक्टर लागू करती है, हर बार इनपुट फ्लिप होने पर 1 और अन्यथा 0 आउटपुट करती है।)


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


==अनुप्रयोग==
==एप्लीकेशन==
मीली मशीनें सिफर मशीनों के लिए एक प्रारंभिक गणितीय मॉडल प्रदान करती हैं। उदाहरण के लिए, [[लैटिन वर्णमाला|लैटिन अल्फाबेट]] के इनपुट और आउटपुट अल्फाबेट को ध्यान में रखते हुए, एक मेयली मशीन डिज़ाइन की जा सकती है जो अक्षरों की एक स्ट्रिंग (इनपुट का एक अनुक्रम) को एक सिफर स्ट्रिंग (आउटपुट का एक अनुक्रम) में संसाधित कर सकती है। हालाँकि, हालांकि [[ पहेली मशीन ]] का वर्णन करने के लिए मीली मॉडल का उपयोग किया जा सकता है, जटिल सिफरिंग मशीनों को डिजाइन करने के व्यवहार्य साधन प्रदान करने के लिए स्टेट आरेख बहुत जटिल होगा।
मीली मशीनें सिफर मशीनों के लिए एक रुदीमेंटरी मैथमेटिकल मॉडल प्रदान करती हैं। उदाहरण के लिए, [[लैटिन वर्णमाला|लैटिन अल्फाबेट]] के इनपुट और आउटपुट अल्फाबेट को ध्यान में रखते हुए, एक मेयली मशीन डिज़ाइन की जा सकती है जो लेटरों की एक स्ट्रिंग (इनपुट का एक अनुक्रम) को एक सिफर स्ट्रिंग (आउटपुट का एक अनुक्रम) में प्रोसेस कर सकती है। हालाँकि,[[ पहेली मशीन | एनिग्मा मशीन]] का वर्णन करने के लिए मीली मॉडल का उपयोग किया जा सकता है, कॉम्प्लेक्स सिफरिंग मशीनों को डिजाइन करने के फीसीबल साधन प्रदान करने के लिए स्टेट डायग्राम बहुत कॉम्प्लेक्स होगा।


मूर/मीली मशीनें [[नियतात्मक परिमित ऑटोमेटन]] हैं जिनका घड़ी की किसी भी टिक पर भी आउटपुट होता है। आधुनिक सीपीयू, कंप्यूटर, सेल फोन, डिजिटल घड़ियां और बुनियादी इलेक्ट्रॉनिक उपकरणों/मशीनों में इसे नियंत्रित करने के लिए कुछ प्रकार की परिमित स्टेट मशीन होती है।
मूर/मीली मशीनें [[नियतात्मक परिमित ऑटोमेटन|डिटर्मिनिस्टिक फाईनाईट ऑटोमेटन]] हैं जिनका क्लॉक की किसी भी टिक पर भी आउटपुट होता है। आधुनिक सीपीयू, कंप्यूटर, सेल फोन, डिजिटल क्लॉक और बेसिक इलेक्ट्रॉनिक उपकरणों/मशीनों में इसे नियंत्रित करने के लिए कुछ प्रकार की परिमित स्टेट मशीन होती है।


सरल सॉफ़्टवेयर सिस्टम, विशेष रूप से वे जिन्हें [[नियमित अभिव्यक्ति]]यों का उपयोग करके दर्शाया जा सकता है, को परिमित स्टेट मशीनों के रूप में मॉडल किया जा सकता है। ऐसी कई सरल प्रणालियाँ हैं, जैसे वेंडिंग मशीन या बुनियादी इलेक्ट्रॉनिक्स।
सिंपल सॉफ़्टवेयर सिस्टम, विशेष रूप से वे जिन्हें [[नियमित अभिव्यक्ति|रेगुलर एक्सप्रेशंस]] का उपयोग करके दर्शाया जा सकता है, फाईनाइट स्टेट मशीनों के रूप में मॉडल किया जा सकता है। ऐसी कई सिंपल सिस्टम हैं, जैसे वेंडिंग मशीन या बेसिक इलेक्ट्रॉनिक्स।


दो परिमित स्टेट मशीनों के प्रतिच्छेदन का पता लगाकर, कोई बहुत ही सरल तरीके से समवर्ती प्रणालियों को डिज़ाइन कर सकता है जो उदाहरण के लिए संदेशों का आदान-प्रदान करते हैं। उदाहरण के लिए, ट्रैफ़िक लाइट एक ऐसी प्रणाली है जिसमें कई उपप्रणालियाँ शामिल होती हैं, जैसे कि विभिन्न ट्रैफ़िक लाइटें, जो एक साथ काम करती हैं।
दो फाईनाईट स्टेट मशीनों के इंटरसेक्शन का पता लगाकर, कोई बहुत ही सिंपल तरीके से कंकररेंट सिस्टम्स को डिज़ाइन कर सकता है जो उदाहरण के लिए मैसेज का आदान-प्रदान करते हैं। उदाहरण के लिए, ट्रैफ़िक लाइट एक ऐसा सिस्टम है जिसमें कई सबसिस्टम सम्मिलित होती हैं, जैसे कि विभिन्न ट्रैफ़िक लाइटें, जो एक साथ काम करती हैं।


अनुप्रयोगों के कुछ उदाहरण:
एप्लीकेशनों के कुछ उदाहरण:
*संख्या वर्गीकरण
*नंबर क्लासिफिकेशन
*टाइमर के साथ देखें
*वेंडिंग मशीन
*व्यापारिक मशीन
*ट्रैफिक - लाइट
*ट्रैफिक - लाइट
*बारकोड स्कैनर
*बारकोड स्कैनर

Revision as of 08:04, 2 August 2023

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

इतिहास

मीली मशीन का नाम जॉर्ज एच. मीली के नाम पर रखा गया है, जिन्होंने 1955 के पेपर, ए मेथड फॉर सिंथेसाइजिंग सीक्वेंशियल सर्किट्स में इस कांसेप्ट को प्रेजेंट किया था। [1]


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

मीली मशीन एक 6-टुपल है निम्नलिखित से मिलकर:

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

कुछ फॉर्मूलेशन में, ट्रांजीशन और आउटपुट फ़ंक्शन को एक ही फ़ंक्शन में संयोजित किया जाता है

मीली मशीनों और मूर मशीनों की तुलना

  1. मीली मशीनों में कम स्टेट होती हैं:
    • आर्क्स पर अलग-अलग आउटपुट (n2) स्टेटों के स्थान पर (एन)।
  2. मूर मशीनों का उपयोग करना अधिक सुरक्षित है:
    • आउटपुट क्लॉक एज पर बदलते हैं (हमेशा एक चक्र बाद में)।
    • मेयली मशीनों में, इनपुट चेंज के कारण लॉजिक होते ही आउटपुट में बदलाव हो सकता है - जब दो मशीनें आपस में जुड़ी होती हैं तो एक बड़ी समस्या होती है - यदि कोई सावधान नहीं है तो एसिंक्रोनस फीडबैक हो सकता है।
  3. मीली मशीनें इनपुट पर तेजी से प्रतिक्रिया करती हैं:
    • एक ही साईकल में रियेक्ट करें—उन्हें क्लॉक का इंतज़ार करने की आवश्यकता नहीं है।
    • मूर मशीनों में, स्टेट को आउटपुट में डिकोड करने के लिए अधिक लॉजिक की आवश्यकता हो सकती है - क्लॉक एज के बाद अधिक गेट डिले।

डायग्राम

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

जब इनपुट और आउटपुट अल्फाबेट दोनों Σ हों, कोई माइली ऑटोमेटा से हेलिक्स डिरेक्टेड ग्राफ (S × Σ, (x, i) → (T(x, i), G(x, i))) भी जोड़ सकता है। [2] इस ग्राफ़ में वेर्टिसेस के रूप में स्टेट और लेटर के पेअर हैं, प्रत्येक नोड आउट-डिग्री एक का है, और (x, i) का सक्सेसर ऑटोमेटा की अगली स्टेट है और वह लेटर जो ऑटोमेटा आउटपुट होता है जब यह x में होता है और यह लेटर i पढ़ता है। यदि ऑटोमेटन बिरेवेर्सिबले है तो यह ग्राफ डिसजोइन्ट साइकल्स का एक यूनियन है।

उदाहरण

सिंपल

एक इनपुट और एक आउटपुट वाली एक साधारण मीली मशीन का डायग्राम बताएं। (प्रत्येक इनपुट वैल्यू के लिए आउटपुट 1, यदि वर्तमान इनपुट वैल्यू पिछले से भिन्न है, या अन्यथा 0।)

एक साधारण मीली मशीन में एक इनपुट और एक आउटपुट होता है। प्रत्येक ट्रांजीशन एज को इनपुट के वैल्यू (लाल रंग में दिखाया गया है) और आउटपुट के वैल्यू (नीले रंग में दिखाया गया है) के साथ लेबल किया गया है। मशीन स्टेट Si में प्रारम्भ होती है। (इस उदाहरण में, आउटपुट दो सबसे हाल के इनपुट वैल्यू का एक्सक्लूसिव-और है; इस प्रकार, मशीन एक एज डिटेक्टर लागू करती है, हर बार इनपुट फ्लिप होने पर 1 और अन्यथा 0 आउटपुट करती है।)

कॉम्प्लेक्स

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

एप्लीकेशन

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

मूर/मीली मशीनें डिटर्मिनिस्टिक फाईनाईट ऑटोमेटन हैं जिनका क्लॉक की किसी भी टिक पर भी आउटपुट होता है। आधुनिक सीपीयू, कंप्यूटर, सेल फोन, डिजिटल क्लॉक और बेसिक इलेक्ट्रॉनिक उपकरणों/मशीनों में इसे नियंत्रित करने के लिए कुछ प्रकार की परिमित स्टेट मशीन होती है।

सिंपल सॉफ़्टवेयर सिस्टम, विशेष रूप से वे जिन्हें रेगुलर एक्सप्रेशंस का उपयोग करके दर्शाया जा सकता है, फाईनाइट स्टेट मशीनों के रूप में मॉडल किया जा सकता है। ऐसी कई सिंपल सिस्टम हैं, जैसे वेंडिंग मशीन या बेसिक इलेक्ट्रॉनिक्स।

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

एप्लीकेशनों के कुछ उदाहरण:

  • नंबर क्लासिफिकेशन
  • वेंडिंग मशीन
  • ट्रैफिक - लाइट
  • बारकोड स्कैनर
  • गैस पंप

यह भी देखें

फ़ुटनोट

  1. Mealy, George H. (September 1955). "अनुक्रमिक सर्किट को संश्लेषित करने की एक विधि". Bell System Technical Journal. 34 (5): 1045–1079. doi:10.1002/j.1538-7305.1955.tb03788.x.
  2. Akhavi et al (2012)

संदर्भ


बाहरी संबंध