मैली मशीन

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

इतिहास

मीली मशीन का नाम जॉर्ज एच. मीली के नाम पर रखा गया है, जिन्होंने 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