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

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

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

विवरण

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

किसी भी सामान्य एल्गोरिदम की परिभाषा में दो भाग होते हैं: यहाँ पर इसके कारण इस एल्गोरिदम की वर्णमाला की परिभाषा के लिए एल्गोरिदम पर इन वर्णमाला में उपयोग किए जाने वाले प्रतीकों की स्ट्रिंग पर लागू किया जाएगा, और इसकी योजना की परिभाषा को परिभाषित किया जाएगा। इस प्रकार सामान्यतः इस एल्गोरिदम की योजना तथाकथित प्रतिस्थापन सूत्रों का सीमित क्रम वाला समुच्चय है, जिनमें से प्रत्येक सरल या अंतिम हो सकता है। इस प्रकार की सरल प्रतिस्थापन सूत्रों को फॉर्म $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. a -> apple
2. b -> bag
3. s -> shop
4. t -> the
5. the shop -> my brother
6. "a never used" -> ."terminating rule"

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

"I bought a B of As from T S."

निष्पादन

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

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