मूर और मेली मशीनें
परिमित ऑटोमेटा में प्रत्येक संक्रमण के अनुरूप आउटपुट हो सकते हैं। दो प्रकार की परिमित राज्य मशीनें हैं जो उत्पादन उत्पन्न करती हैं -
- मैली मशीन
- मूर मशीन
मैली मशीन
Mealy मशीन एक FSM है जिसका उत्पादन वर्तमान स्थिति के साथ-साथ वर्तमान इनपुट पर निर्भर करता है।
इसका वर्णन 6 टुपल (Q, a, O, X, X, q 0 ) द्वारा किया जा सकता है जहां -
Q राज्यों का एक समुच्चय है।
∑ इनपुट वर्णमाला नामक प्रतीकों का एक परिमित सेट है।
O आउटपुट वर्णमाला नामक प्रतीकों का एक सीमित सेट है।
δ इनपुट संक्रमण फ़ंक्शन है जहां δ: Q ×। → Q
X आउटपुट संक्रमण फ़ंक्शन है जहां X: Q × output → O
q0वह प्रारंभिक अवस्था है जहां से किसी भी इनपुट को संसाधित किया जाता है (q 0 ) Q)।
एक मेयली मशीन की राज्य तालिका नीचे दिखाई गई है -
वर्तमान स्थिति | अगली अवस्था | |||
---|---|---|---|---|
इनपुट = ० | इनपुट = १ | |||
राज्य | उत्पादन | राज्य | उत्पादन | |
→ ए | ख | x 1 | सी | x 1 |
ख | ख | x 2 | घ | x 3 |
सी | घ | x 3 | सी | x 1 |
घ | घ | x 3 | घ | x 2 |
उपरोक्त मेयली मशीन का राज्य आरेख है -
मूर मशीन
मूर मशीन एक FSM है जिसका आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है।
एक मूर मशीन को 6 टुपल (Q, be, O, machine, X, q 0 ) द्वारा वर्णित किया जा सकता है जहां -
Q राज्यों का एक समुच्चय है।
∑ इनपुट वर्णमाला नामक प्रतीकों का एक परिमित सेट है।
O आउटपुट वर्णमाला नामक प्रतीकों का एक सीमित सेट है।
δ इनपुट संक्रमण फ़ंक्शन है जहां δ: Q ×। → Q
X आउटपुट संक्रमण फ़ंक्शन है जहां X: Q → O
q0वह प्रारंभिक अवस्था है जहां से किसी भी इनपुट को संसाधित किया जाता है (q 0 ) Q)।
मूर मशीन की राज्य तालिका नीचे दिखाई गई है -
वर्तमान स्थिति | अगला राज्य | उत्पादन | |
---|---|---|---|
इनपुट = ० | इनपुट = 1 | ||
→ ए | ख | सी | x 2 |
ख | ख | घ | x 1 |
सी | सी | घ | x 2 |
घ | घ | घ | x 3 |
उपरोक्त मूर मशीन का राज्य आरेख है -
मेली मशीन बनाम मूर मशीन
निम्न तालिका उन बिंदुओं पर प्रकाश डालती है जो मूर मशीन से एक मेयली मशीन को अलग करती हैं।
मैली मशीन | मूर मशीन |
---|---|
आउटपुट वर्तमान स्थिति और वर्तमान इनपुट दोनों पर निर्भर करता है | आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है। |
आम तौर पर, इसमें मूर मशीन की तुलना में कम राज्य होते हैं। | आम तौर पर, इसमें मेयली मशीन की तुलना में अधिक राज्य होते हैं। |
आउटपुट फ़ंक्शन का मान संक्रमणों और परिवर्तनों का एक फ़ंक्शन है, जब वर्तमान स्थिति पर इनपुट तर्क किया जाता है। | आउटपुट फ़ंक्शन का मान वर्तमान स्थिति और घड़ी के किनारों पर परिवर्तन का एक फ़ंक्शन है, जब भी राज्य परिवर्तन होते हैं। |
Mealy मशीन इनपुट पर तेजी से प्रतिक्रिया करती हैं। वे आम तौर पर एक ही घड़ी चक्र में प्रतिक्रिया करते हैं। | मूर मशीनों में, अधिक सर्किट देरी के परिणामस्वरूप आउटपुट को डीकोड करने के लिए अधिक तर्क की आवश्यकता होती है। वे आम तौर पर एक घड़ी चक्र के बाद प्रतिक्रिया करते हैं। |
मूर मशीन टू मेयली मशीन
एल्गोरिथम 4
Input - मूर मशीन
Output - मैली मशीन
Step 1 - खाली Mealy मशीन संक्रमण तालिका प्रारूप लें।
Step 2 - सभी मूर मशीन संक्रमण को इस तालिका प्रारूप में कॉपी करें।
Step 3- मूर मशीन राज्य तालिका में वर्तमान राज्यों और उनके संबंधित आउटपुट की जांच करें; अगर एक राज्य क्यू के लिए मैं उत्पादन मीटर है, यह आटे मशीन राज्य तालिका के उत्पादन में स्तंभों में कॉपी जहाँ भी क्यू मैं अगले राज्य में प्रकट होता है।
उदाहरण
आइए निम्नलिखित मूर मशीन पर विचार करें -
वर्तमान स्थिति | अगला राज्य | उत्पादन | |
---|---|---|---|
a = ० | a = १ | ||
→ ए | घ | ख | 1 |
ख | ए | घ | 0 |
सी | सी | सी | 0 |
घ | ख | ए | 1 |
अब हम इसे Mealy Machine में बदलने के लिए Algorithm 4 लागू करते हैं।
Step 1 & 2 -
वर्तमान स्थिति | अगला राज्य | |||
---|---|---|---|---|
a = ० | a = १ | |||
राज्य | उत्पादन | राज्य | उत्पादन | |
→ ए | घ | ख | ||
ख | ए | घ | ||
सी | सी | सी | ||
घ | ख | ए |
Step 3 -
वर्तमान स्थिति | अगला राज्य | |||
---|---|---|---|---|
a = ० | a = १ | |||
राज्य | उत्पादन | राज्य | उत्पादन | |
=> ए | घ | 1 | ख | 0 |
ख | ए | 1 | घ | 1 |
सी | सी | 0 | सी | 0 |
घ | ख | 0 | ए | 1 |
Mealy मशीन मूर मशीन के लिए
एल्गोरिथ्म 5
Input - मैली मशीन
Output - मूर मशीन
Step 1- प्रत्येक राज्य (क्यू i ) के लिए अलग-अलग आउटपुट की संख्या की गणना करें जो मेयली मशीन के राज्य तालिका में उपलब्ध हैं।
Step 2- सभी क्यूई के आउटपुट में एक ही कर रहे हैं, नकल राज्य क्यू मैं । यदि इसमें n अलग-अलग आउटपुट हैं, तो Q i को n राज्यों में तोड़ दें जहां Q हैn = 0, 1, 2 ......।
Step 3 - यदि प्रारंभिक अवस्था का आउटपुट 1 है, तो शुरुआत में एक नया प्रारंभिक राज्य डालें, जो 0 आउटपुट देता है।
उदाहरण
आइए निम्नलिखित मेली मशीन पर विचार करें -
वर्तमान स्थिति | अगला राज्य | |||
---|---|---|---|---|
a = ० | a = १ | |||
अगला राज्य | उत्पादन | अगला राज्य | उत्पादन | |
→ ए | घ | 0 | ख | 1 |
ख | ए | 1 | घ | 0 |
सी | सी | 1 | सी | 0 |
घ | ख | 0 | ए | 1 |
यहाँ, 'a' और 'd' क्रमशः केवल 1 और 0 आउटपुट देते हैं, इसलिए हम 'a' और 'd' राज्यों को बनाए रखते हैं। लेकिन राज्यों 'बी' और 'सी' विभिन्न आउटपुट (1 और 0) का उत्पादन करते हैं। इसलिए, हम विभाजित करते हैंb जांच b0, b1 तथा c जांच c0, c1।
वर्तमान स्थिति | अगला राज्य | उत्पादन | |
---|---|---|---|
a = ० | a = १ | ||
→ ए | घ | बी १ | 1 |
बी ० | ए | घ | 0 |
बी १ | ए | घ | 1 |
ग ० | ग १ | सी ० | 0 |
ग १ | ग १ | सी ० | 1 |
घ | बी ० | ए | 0 |