मार्कोव एल्गोरिथ्म: Difference between revisions

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


रिफ़ल मार्कोव एल्गोरिदम पर आधारित [[प्रोग्रामिंग भाषा]] है।
रिफ़ल मार्कोव एल्गोरिदम पर आधारित [[प्रोग्रामिंग भाषा]] है।
Line 5: Line 5:
==विवरण==
==विवरण==


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


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


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


: <math>\left\{\begin{matrix} |b&\to& ba|\\ ab&\to& ba\\ b&\to&\\ {*}|&\to& b*& \\ {*}&\to& c& \\
: <math>\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.</math>
|c&\to& c\\ ac&\to& c|\\ c&\to\cdot\end{matrix}\right.</math>
एक मनमानी स्ट्रिंग पर सामान्य एल्गोरिदम लागू करने की प्रक्रिया <math>V</math> इस एल्गोरिथ्म की वर्णमाला में प्रारंभिक चरणों का अलग क्रम है, जिसमें निम्नलिखित शामिल हैं। चलिए मान लेते हैं <math>V'</math> एल्गोरिथम के पिछले चरण में प्राप्त शब्द है (या मूल शब्द <math>V</math>, यदि वर्तमान चरण पहला है)। यदि प्रतिस्थापन सूत्रों में कोई बायां पक्ष नहीं है जो इसमें शामिल है <math>V'</math>, तो एल्गोरिथ्म समाप्त हो जाता है, और इसके कार्य का परिणाम स्ट्रिंग माना जाता है <math>V'</math>. अन्यथा, प्रतिस्थापन सूत्रों में से पहला जिसके बाएँ पक्ष शामिल हैं <math>V'</math> चयनित है। यदि प्रतिस्थापन सूत्र रूप का है <math>L\to\cdot D</math>, फिर स्ट्रिंग के सभी संभावित अभ्यावेदन में से <math>V'</math> रूप का <math>RLS</math> (कहाँ <math>R</math> और <math>S</math> मनमाना तार हैं) सबसे छोटा वाला <math>R</math> चुना जाता है। फिर एल्गोरिदम समाप्त हो जाता है और उसके कार्य का परिणाम माना जाता है <math>RDS</math>. हालाँकि, यदि यह प्रतिस्थापन सूत्र फॉर्म का है <math>L\to D</math>, फिर स्ट्रिंग के सभी संभावित अभ्यावेदन में से <math>V'</math> के रूप का <math>RLS</math> सबसे छोटा वाला <math>R</math> चुना जाता है, जिसके बाद स्ट्रिंग <math>RDS</math> इसे वर्तमान चरण का परिणाम माना जाता है, जो अगले चरण में आगे की प्रक्रिया के अधीन है।
इस प्रकार की स्ट्रिंग पर सामान्य एल्गोरिदम को लागू करने की प्रक्रिया <math>V</math> इस एल्गोरिथ्म की वर्णमाला में प्रारंभिक चरणों का अलग क्रम है, जिसमें निम्नलिखित मानों को सम्मिलित किया जाता हैं। इस प्रकार हम यह मान लेते हैं कि <math>V'</math> एल्गोरिथम के पिछले चरण में प्राप्त शब्द या मूल शब्द <math>V</math> है, यहाँ पर ध्यान देने वाली बात यह हैं कि यह यदि वर्तमान चरण का पहला भाग है। यदि प्रतिस्थापन सूत्रों में कोई बायां पक्ष नहीं है जो इसमें <math>V'</math> सम्मिलित है, तो एल्गोरिथ्म समाप्त हो जाता है, और इसके कार्य का परिणाम स्ट्रिंग <math>V'</math> माना जाता है, अन्यथा, प्रतिस्थापन सूत्रों में से पहला जिसके बाएँ पक्ष सम्मिलित हैं, जिसके लिए <math>V'</math> को चयनित करते है। यदि प्रतिस्थापन सूत्र <math>L\to\cdot D</math> रूप का है, तो पुनः इस स्ट्रिंग के सभी संभावित अभ्यावेदन में से <math>V'</math> रूप का <math>RLS</math> जहाँ <math>R</math> और <math>S</math> मनमाना स्ट्रिंग हैं, इसका सबसे छोटा मान <math>R</math> चुना जाता है। फिर एल्गोरिदम समाप्त हो जाता है और उसके कार्य का परिणाम <math>RDS</math> माना जाता है, चूंकि, यदि यह प्रतिस्थापन सूत्र का फॉर्म <math>L\to D</math> है, इसके पश्चात पुनः इस स्ट्रिंग के सभी संभावित अभ्यावेदन में से <math>V'</math> के रूप का <math>RLS</math> सबसे छोटा वाला <math>R</math> चुना जाता है, जिसके पश्चात स्ट्रिंग <math>RDS</math> के लिए इसे वर्तमान चरण का परिणाम माना जाता है, जो अगले चरण में आगे की प्रक्रिया के अधीन है।


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


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


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


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


==एल्गोरिदम==
==एल्गोरिदम==


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


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


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


==उदाहरण==
==उदाहरण==
Line 41: Line 41:


===नियम===
===नियम===
# ए -> सेब
# a -> apple
# बी -> बैग
# b -> bag
# एस -> दुकान
# s -> shop
# टी -> द
# t -> the
# दुकान -> मेरा भाई
# the shop -> my brother
# a कभी उपयोग नहीं किया गया -> . समाप्ति नियम
# "a never used" -> '''.'''"terminating rule"


===प्रतीक स्ट्रिंग===
===प्रतीक स्ट्रिंग===
  मैंने टी एस से एज़ का बी खरीदा।
  "I bought a B of As from T S."


===निष्पादन===
===निष्पादन===
Line 61: Line 61:
#मैंने अपने भाई से सेब का बैग खरीदा।
#मैंने अपने भाई से सेब का बैग खरीदा।


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


==एक और उदाहरण==
==अन्य उदाहरण==


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


===नियम===
===नियम===

Revision as of 22:58, 25 July 2023

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

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

विवरण

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

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

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

इस प्रकार की स्ट्रिंग पर सामान्य एल्गोरिदम को लागू करने की प्रक्रिया इस एल्गोरिथ्म की वर्णमाला में प्रारंभिक चरणों का अलग क्रम है, जिसमें निम्नलिखित मानों को सम्मिलित किया जाता हैं। इस प्रकार हम यह मान लेते हैं कि एल्गोरिथम के पिछले चरण में प्राप्त शब्द या मूल शब्द है, यहाँ पर ध्यान देने वाली बात यह हैं कि यह यदि वर्तमान चरण का पहला भाग है। यदि प्रतिस्थापन सूत्रों में कोई बायां पक्ष नहीं है जो इसमें सम्मिलित है, तो एल्गोरिथ्म समाप्त हो जाता है, और इसके कार्य का परिणाम स्ट्रिंग माना जाता है, अन्यथा, प्रतिस्थापन सूत्रों में से पहला जिसके बाएँ पक्ष सम्मिलित हैं, जिसके लिए को चयनित करते है। यदि प्रतिस्थापन सूत्र रूप का है, तो पुनः इस स्ट्रिंग के सभी संभावित अभ्यावेदन में से रूप का जहाँ और मनमाना स्ट्रिंग हैं, इसका सबसे छोटा मान चुना जाता है। फिर एल्गोरिदम समाप्त हो जाता है और उसके कार्य का परिणाम माना जाता है, चूंकि, यदि यह प्रतिस्थापन सूत्र का फॉर्म है, इसके पश्चात पुनः इस स्ट्रिंग के सभी संभावित अभ्यावेदन में से के रूप का सबसे छोटा वाला चुना जाता है, जिसके पश्चात स्ट्रिंग के लिए इसे वर्तमान चरण का परिणाम माना जाता है, जो अगले चरण में आगे की प्रक्रिया के अधीन है।

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

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

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

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

एल्गोरिदम

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

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

  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[1])
  1. ↑ Kushner, Boris A. (1999-05-28). "Markov's constructive analysis; a participant's view". Theoretical Computer Science (in English). 219 (1–2): 268, 284. doi:10.1016/S0304-3975(98)00291-6.

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=मार्कोव_एल्गोरिथ्म&oldid=230370’