मैली मशीन

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

इतिहास

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

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

मीली मशीन एक 6-टुपल $(S,S_{0},\Sigma ,\Lambda ,T,G)$ है निम्नलिखित से मिलकर:

• स्टेट का एक फाईनाईट सेट (कंप्यूटर विज्ञान) $S$
• एक स्टार्ट स्टेट (जिसे आरंभिक अवस्था भी कहा जाता है) $S_{0}$ जो कि एक एलिमेंट $S$ है
• एक फाईनाईट सेट जिसे इनपुट अल्फाबेट (कंप्यूटर विज्ञान) $\Sigma$ कहा जाता है
• एक फाईनाईट सेट जिसे आउटपुट अल्फाबेट $\Lambda$ (कंप्यूटर विज्ञान) कहा जाता है
• एक ट्रांजीशन फंक्शन (गणित) $T:S\times \Sigma \rightarrow S$ एक स्टेट के पेअर और एक इनपुट सिंबल को करेस्पोंडिंग अगले स्टेट में मैप करना।
• एक आउटपुट फ़ंक्शन $G:S\times \Sigma \rightarrow \Lambda$ एक स्टेट और एक इनपुट सिंबल के पेअर को करेस्पोंडिंग आउटपुट सिंबल में मैप करना।

कुछ फॉर्मूलेशन में, ट्रांजीशन और आउटपुट फ़ंक्शन को एक ही फ़ंक्शन में संयोजित किया जाता है $T:S\times \Sigma \rightarrow S\times \Lambda$।

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

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

डायग्राम

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

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

उदाहरण

सिंपल

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

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

कॉम्प्लेक्स

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

एप्लीकेशन

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

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

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

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

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

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

यह भी देखें

• सिंक्रोनस सर्किट
• मूर मशीन
• एल्गोरिथम स्टेट मशीन
• रिचर्ड्स नियंत्रक

संदर्भ

• Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079.
• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
• Roth, Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. pp. 364–367. ISBN 0-534-37804-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). "On the finiteness problem for automaton (semi)groups". International Journal of Algebra and Computation. 22 (6). arXiv:1105.4725. Bibcode:2011arXiv1105.4725A. doi:10.1142/S021819671250052X. S2CID 47518684. Zbl 1280.20038.

बाहरी संबंध

• Media related to मैली मशीन at Wikimedia Commons