सेमी-थू प्रणाली

सैद्धांतिक कंप्यूटर विज्ञान और गणितीय तर्क में स्ट्रिंग पुनर्लेखन प्रणाली (एसआरएस), जिसे ऐतिहासिक रूप से सेमी-एक्सल थ्यू प्रणाली कहा जाता है, सामान्यतः इसे परिमित समुच्चय में वर्णमाला (कंप्यूटर विज्ञान) से स्ट्रिंग (कंप्यूटर विज्ञान) पर पुनर्लेखन प्रणाली के लिए भी जाना जाता है। इस प्रकार इसमें बाइनरी संबंध भी उपयोग किया जाता है, जो $R$ वर्णमाला पर निश्चित स्ट्रिंग के बीच, जिसे पुनर्लेखन नियम कहा जाता है, इसे $s\rightarrow t$ के द्वारा दर्शाया जाता है, इसके आधार पर एसआरएस सभी स्ट्रिंग्स के लिए पुनर्लेखन संबंध का विस्तार करता है जिसमें नियमों के बाएँ और दाएँ ओर सबस्ट्रिंग भी दिखाई देती हैं, अर्थात $usv\rightarrow utv$, जहाँ $s$, $t$, $u$, और $v$ स्ट्रिंग के रूप में हैं।

यहाँ पर सेमी-थ्यू प्रणाली की मुख्य धारणा अनिवार्यतः मोनॉइड की प्रस्तुति से मेल खाती है। इस प्रकार ऐसे मोनोइड्स और समुच्चयों के लिए शब्द समस्या (गणित) को हल करने के लिए प्राकृतिक रूपरेखा बनायी जाती हैं।

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

परिभाषा

किसी स्ट्रिंग के पुनर्लेखन प्रणाली या सेमी-थ्यू प्रणाली को टपल $(\Sigma ,R)$ कहा जाता है, जहाँ पर इन मुख्य बिंदुओं पर ध्यान दिया जाता हैं जो इस प्रकार हैं-

• Σ वर्णमाला है, जिसे सामान्यतः सीमित वर्णमाला माना जाता है। इस प्रकार के समुच्चयओं के लिए तत्व $\Sigma ^{*}$ का उपयोग किया जाता हैं, यहां पर क्लेन स्टार * का उपयोग किया जाता है, इस प्रकार परिमित संभवतः रिक्त स्ट्रिंग Σ का उदाहरण हैं, जिसे कभी-कभी औपचारिक भाषाओं में शब्द भी कहा जाता है, हम यहाँ पर इन्हें बस स्ट्रिंग्स कहते हैं।
• R स्ट्रिंग्स पर बाइनरी संबंध Σ द्वारा प्रदर्शित होता है, अर्थात $R\subseteq \Sigma ^{*}\times \Sigma ^{*}.$ इसमें पाये जाने वाले प्रत्येक तत्व $(u,v)\in R$ के लिए इसे उचित पुनर्लेखन नियम के रूप से जाना जाता है, और इसे सामान्यतः $u\rightarrow v$ इस प्रकार लिखा जाता है।

यदि संबंध R सममित संबंध को प्रदर्शित करता है, तो इस प्रणाली को थ्यू प्रणाली कहा जाता है।

इसमें पुनर्लेखन नियम R को स्वाभाविक रूप से अन्य स्ट्रिंग्स $\Sigma ^{*}$ तक बढ़ाया जा सकता है, जिसके अनुसार सबस्ट्रिंग को पुनः R द्वारा लिखने की अनुमति देकर इसे अधिकांशतः औपचारिक रूप से वन फेस पुनर्लेखन संबंध ${\xrightarrow[{R}]{}}$ प्रेरक R पर $\Sigma ^{*}$ किसी भी स्ट्रिंग $s,t\in \Sigma ^{*}$ के लिए इस प्रकार प्रदर्शित होता हैं :

इस प्रकार $s{\xrightarrow[{R}]{}}t$ होने पर यदि $x,y,u,v\in \Sigma ^{*}$ मान प्राप्त होता हैं जो इस प्रकार है कि- $s=xuy$, $t=xvy$, और $u\rightarrow v$ के समान होता हैं।

इस स्थिति में ${\xrightarrow[{R}]{}}$ पर रिलेशन $x,y,u,v\in \Sigma ^{*}$ प्राप्त होता हैं, यहाँ पर संयुग्म $(\Sigma ^{*},{\xrightarrow[{R}]{}})$ स्यूडो पुनर्लेखन प्रणाली की परिभाषा में फिट बैठता है। सामान्यतः R का उपसमुच्चय ${\xrightarrow[{R}]{}}$ है, इसके आधार पर यहाँ पर कुछ लेखक इन एरों के लिए ${\xrightarrow[{R}]{}}$ (उदा ${\xrightarrow[{R}]{}}$) संकेतन का उपयोग करते हैं, इसे अलग करने के लिए R स्वयं अपने आप ($\rightarrow$) द्वारा प्रदर्शित होता हैं। क्योंकि वे इसके पश्चात सबस्क्रिप्ट को छोड़ने में सक्षम होना चाहते हैं और फिर भी बीच में R से उत्पन्न होने वाले भ्रम से बचना चाहते हैं, और वन-फेस R वाले पुनर्लेखन से प्रेरित होते हैं।

स्पष्ट रूप से सेमी-थ्यू प्रणाली में हम प्रारंभिक स्ट्रिंग से प्रारंभ करके उत्पादित स्ट्रिंग्स का परिमित या अनंत अनुक्रम $s_{0}\in \Sigma ^{*}$ बना सकते हैं, और इस समय सबस्ट्रिंग-प्रतिस्थापन करके इसे बार-बार दोबारा लिखा जाता हैं:

$s_{0}\ {\xrightarrow[{R}]{}}\ s_{1}\ {\xrightarrow[{R}]{}}\ s_{2}\ {\xrightarrow[{R}]{}}\ \ldots$

इस प्रकार के शून्य-या-अधिक-चरणों वाले पुनर्लेखन को प्रतिवर्ती सकर्मक समापन ${\xrightarrow[{R}]{}}$ द्वारा कैप्चर किया जाता है, ${\xrightarrow[{R}]{*}}$ द्वारा चिह्नित इस अर्थ को पुनर्लेखन प्रणाली में मौलिक धारणाओं पर देखा जा सकता हैं। इसे पुनर्लेखन संबंध या न्यूनीकरण संबंध $\Sigma ^{*}$ प्रेरक R कहा जाता है।

थ्यू सर्वांगसमता

सामान्यतः समुच्चय $\Sigma ^{*}$ वर्णमाला पर स्ट्रिंग्स की संख्या में उपस्थित होने वाले स्ट्रिंग संयोजन के लिए उपयुक्त बाइनरी ऑपरेशन के साथ मिलकर मुक्त मोनॉइड बनाते है, जिसे इस रूप में दर्शाया गया है। यहाँ पर प्रतीक को हटाकर गुणनात्मक रूप से लिखा जाता है। इस प्रकार एसआरएस में होने वाली कमी ${\xrightarrow[{R}]{*}}$ के संबंध को मोनॉइड ऑपरेशन के साथ संगत किया जाता है, जिसका अर्थ $x{\xrightarrow[{R}]{*}}y$ है, जिसका तात्पर्य $uxv{\xrightarrow[{R}]{*}}uyv$ के लिए इसमें पाये जाने वाले सभी स्ट्रिंग के लिए $x,y,u,v\in \Sigma ^{*}$ हैं। जहाँ पर ${\xrightarrow[{R}]{*}}$ की परिभाषा के अनुसार पूर्व आदेश प्राप्त होते है, इस प्रकार $($