मार्कोव एल्गोरिथ्म

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

रिफ़ल मार्कोव एल्गोरिदम पर आधारित एक प्रोग्रामिंग भाषा है।

विवरण

सामान्य एल्गोरिदम मौखिक होते हैं, यानी, विभिन्न वर्णमाला में स्ट्रिंग्स पर लागू करने का इरादा रखते हैं।

किसी भी सामान्य एल्गोरिदम की परिभाषा में दो भाग होते हैं: एल्गोरिदम की वर्णमाला की परिभाषा (एल्गोरिदम इन वर्णमाला प्रतीकों की स्ट्रिंग पर लागू किया जाएगा), और इसकी योजना की परिभाषा। सामान्य एल्गोरिदम की योजना तथाकथित प्रतिस्थापन सूत्रों का एक सीमित क्रम वाला सेट है, जिनमें से प्रत्येक सरल या अंतिम हो सकता है। सरल प्रतिस्थापन सूत्रों को फॉर्म की स्ट्रिंग्स द्वारा दर्शाया जाता है $L\to D$, कहाँ $L$ और $D$ एल्गोरिथम की वर्णमाला में दो मनमाने तार हैं (जिन्हें क्रमशः सूत्र प्रतिस्थापन के बाएँ और दाएँ पक्ष कहा जाता है)। इसी प्रकार, अंतिम प्रतिस्थापन सूत्रों को फॉर्म की स्ट्रिंग्स द्वारा दर्शाया जाता है $L\to \cdot D$, कहाँ $L$ और $D$ एल्गोरिथम की वर्णमाला में दो मनमाने तार हैं। यह मानता है कि सहायक पात्र $\to$ और $\to \cdot$ एल्गोरिथम की वर्णमाला से संबंधित नहीं हैं (अन्यथा बाएँ और दाएँ पक्ष के विभाजक के रूप में अपनी भूमिका निभाने के लिए दो अन्य वर्ण, जो एल्गोरिथम की वर्णमाला में नहीं हैं, का चयन किया जाना चाहिए)।

यहां पांच अक्षरों वाली वर्णमाला में एक सामान्य एल्गोरिदम योजना का एक उदाहरण दिया गया है $|*abc$:

$\left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.$

एक मनमानी स्ट्रिंग पर सामान्य एल्गोरिदम लागू करने की प्रक्रिया $V$ इस एल्गोरिथ्म की वर्णमाला में प्रारंभिक चरणों का एक अलग क्रम है, जिसमें निम्नलिखित शामिल हैं। चलिए मान लेते हैं $V'$ एल्गोरिथम के पिछले चरण में प्राप्त शब्द है (या मूल शब्द $V$, यदि वर्तमान चरण पहला है)। यदि प्रतिस्थापन सूत्रों में कोई बायां पक्ष नहीं है जो इसमें शामिल है $V'$, तो एल्गोरिथ्म समाप्त हो जाता है, और इसके कार्य का परिणाम स्ट्रिंग माना जाता है $V'$. अन्यथा, प्रतिस्थापन सूत्रों में से पहला जिसके बाएँ पक्ष शामिल हैं $V'$ चयनित है। यदि प्रतिस्थापन सूत्र रूप का है $L\to \cdot D$, फिर स्ट्रिंग के सभी संभावित अभ्यावेदन में से $V'$ रूप का $RLS$ (कहाँ $R$ और $S$ मनमाना तार हैं) सबसे छोटा वाला $R$ चुना जाता है। फिर एल्गोरिदम समाप्त हो जाता है और उसके कार्य का परिणाम माना जाता है $RDS$. हालाँकि, यदि यह प्रतिस्थापन सूत्र फॉर्म का है $L\to D$, फिर स्ट्रिंग के सभी संभावित अभ्यावेदन में से $V'$ के रूप का $RLS$ सबसे छोटा वाला $R$ चुना जाता है, जिसके बाद स्ट्रिंग $RDS$ इसे वर्तमान चरण का परिणाम माना जाता है, जो अगले चरण में आगे की प्रक्रिया के अधीन है।

उदाहरण के लिए, ऊपर वर्णित एल्गोरिदम को शब्द पर लागू करने की प्रक्रिया $|*||$ शब्दों के क्रम में परिणाम होता है $|b*|$, $ba|*|$, $a|*|$, $a|b*$, $aba|*$, $baa|*$, $aa|*$, $aa|c$, $aac$, $ac|$ और $c||$, जिसके बाद एल्गोरिदम परिणाम के साथ बंद हो जाता है $||$.

अन्य उदाहरणों के लिए, नीचे देखें।

कोई भी सामान्य एल्गोरिदम कुछ ट्यूरिंग मशीन के बराबर है, और इसके विपरीत – कोई भी ट्यूरिंग मशीन कुछ सामान्य एल्गोरिदम के बराबर है। सामान्य एल्गोरिदम के संबंध में तैयार चर्च-ट्यूरिंग थीसिस के एक संस्करण को सामान्यीकरण का सिद्धांत कहा जाता है।

रचनात्मक गणित के कई अनुभागों के निर्माण के लिए सामान्य एल्गोरिदम एक सुविधाजनक साधन साबित हुए हैं। इसके अलावा, सामान्य एल्गोरिदम की परिभाषा में प्रतीकात्मक जानकारी को संभालने के उद्देश्य से प्रोग्रामिंग भाषाओं में उपयोग किए जाने वाले कई विचार अंतर्निहित हैं – उदाहरण के लिए, रिफ़ल में।

एल्गोरिदम

नियम तारों के जोड़े का एक क्रम है, जिसे आमतौर पर पैटर्न → प्रतिस्थापन के रूप में प्रस्तुत किया जाता है। प्रत्येक नियम या तो सामान्य या अंतिम हो सकता है।

एक इनपुट स्ट्रिंग दिया गया:

1. यह देखने के लिए कि इनपुट स्ट्रिंग में कोई पैटर्न पाया जा सकता है या नहीं, नियमों को ऊपर से नीचे तक क्रम में जांचें।
2. यदि कोई नहीं मिलता है, तो एल्गोरिदम रुक जाता है।
3. यदि एक (या अधिक) पाया जाता है, तो इनपुट स्ट्रिंग में मिलान किए गए पाठ की सबसे बाईं ओर की घटना को उसके प्रतिस्थापन के साथ बदलने के लिए उनमें से 'पहले' का उपयोग करें।
4. यदि अभी लागू किया गया नियम समाप्ति वाला है, तो एल्गोरिथम रुक जाता है।
5. चरण 1 पर जाएँ.

ध्यान दें कि प्रत्येक नियम के आवेदन के बाद खोज पहले नियम से शुरू होती है।

उदाहरण

निम्नलिखित उदाहरण मार्कोव एल्गोरिथम के मूल संचालन को दर्शाता है।

नियम

1. ए -> सेब
2. बी -> बैग
3. एस -> दुकान
4. टी -> द
5. दुकान -> मेरा भाई
6. a कभी उपयोग नहीं किया गया -> . समाप्ति नियम

प्रतीक स्ट्रिंग

मैंने टी एस से एज़ का बी खरीदा।

निष्पादन

यदि एल्गोरिथ्म को उपरोक्त उदाहरण पर लागू किया जाता है, तो प्रतीक स्ट्रिंग निम्नलिखित तरीके से बदल जाएगी।

1. मैंने टी एस से एज़ का बी खरीदा।
2. मैंने टी एस से सेब का बी खरीदा।
3. मैंने टी एस से सेब का एक बैग खरीदा।
4. मैंने टी दुकान से सेब का एक बैग खरीदा।
5. मैंने दुकान से सेब का एक बैग खरीदा।
6. मैंने अपने भाई से सेब का एक बैग खरीदा।

इसके बाद एल्गोरिथम समाप्त हो जाएगा.

एक और उदाहरण

ये नियम एक और दिलचस्प उदाहरण देते हैं. वे बाइनरी संख्याओं को उनके एकात्मक समकक्षों में फिर से लिखते हैं। उदाहरण के लिए, 101 को लगातार 5 बार की एक स्ट्रिंग में फिर से लिखा जाएगा।

नियम

1. |0 -> 0||
2. 1 -> 0|
3. 0 ->

प्रतीक स्ट्रिंग

101

निष्पादन

यदि एल्गोरिथ्म को उपरोक्त उदाहरण पर लागू किया जाता है, तो यह निम्नलिखित चरणों के बाद समाप्त हो जाएगा।

1. 101
2. 0|01
3. 00||1
4. 00||0|
5. 00|0|||
6. 000|||||
7. 00|||||
8. 0|||||
9. |||||

यह भी देखें

• थू (प्रोग्रामिंग भाषा)
• औपचारिक व्याकरण

संदर्भ

• Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
• Andrey Andreevich Markov (1903-1979) 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189)

बाहरी संबंध

• Yad Studio - Markov algorithms IDE and interpreter (Open Source)
• Markov algorithm interpreter
• Markov algorithm interpreter
• Markov algorithm interpreters at Rosetta-Code