स्ट्रिंग ऑपरेशन

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

स्ट्रिंग्स और भाषाएँ

एक रज्जु वर्णों का एक सीमित अनुक्रम है। खाली रज्जु को इसके द्वारा निरूपित किया जाता है $\varepsilon$. दो तारों का संयोजन $s$ और $t$ द्वारा निरूपित किया जाता है $s\cdot t$, या इससे छोटा $st$. खाली रज्जु के साथ संयोजन करने से कोई फर्क नहीं पड़ता: $s\cdot \varepsilon =s=\varepsilon \cdot s$. तारों का संयोजन साहचर्य है: $s\cdot (t\cdot u)=(s\cdot t)\cdot u$.

उदाहरण के लिए, $(\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle$.

एक भाषा (कंप्यूटर विज्ञान) स्ट्रिंग्स का एक सीमित या अनंत सेट है। यूनियन, इंटरसेक्शन आदि जैसे सामान्य सेट ऑपरेशन के अलावा, कॉन्सटेनेशन को भाषाओं पर लागू किया जा सकता है: अगर दोनों $S$ और $T$ भाषाएँ हैं, उनका संयोजन है $S\cdot T$ किसी भी रज्जु के संयोजन के सेट के रूप में परिभाषित किया गया है $S$ और किसी भी रज्जु से $T$, औपचारिक रूप से $S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}$. पुनः, सम्मिलन बिंदु $\cdot$ संक्षिप्तता के लिए अक्सर छोड़ दिया जाता है।

भाषा $\{\varepsilon \}$ केवल खाली रज्जु को खाली भाषा से अलग करना है $\{\}$. किसी भी भाषा को पहली भाषा के साथ जोड़ने से कोई परिवर्तन नहीं होता है: $S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S$, जबकि उत्तरार्द्ध के साथ संयोजन करने पर हमेशा खाली भाषा उत्पन्न होती है: $S\cdot \{\}=\{\}=\{\}\cdot S$. भाषाओं का संयोजन साहचर्य है: $S\cdot (T\cdot U)=(S\cdot T)\cdot U$.

उदाहरण के लिए, संक्षिप्त करना $D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}$, सभी तीन अंकों वाली दशमलव संख्याओं का समुच्चय इस प्रकार प्राप्त होता है $D\cdot D\cdot D$. मनमानी लंबाई की सभी दशमलव संख्याओं का सेट एक अनंत भाषा के लिए एक उदाहरण है।

एक रज्जु की वर्णमाला

एक रज्जु की वर्णमाला उन सभी वर्णों का समूह है जो एक विशेष रज्जु में होते हैं। यदि s एक रज्जु है, तो इसका वर्णमाला (कंप्यूटर विज्ञान) द्वारा दर्शाया जाता है

$\operatorname {Alph} (s)$

किसी भाषा की वर्णमाला $S$ किसी भी रज्जु में आने वाले सभी वर्णों का समूह है $S$, औपचारिक रूप से: $\operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)$.

उदाहरण के लिए, सेट $\{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}$ रज्जु का वर्णमाला है $\langle cacao\rangle$, और #स्ट्रिंग्स_और_भाषाएँ $D$ #स्ट्रिंग्स_एंड_लैंग्वेजेज भाषा की वर्णमाला है $D\cdot D\cdot D$ साथ ही सभी दशमलव संख्याओं की भाषा भी।

रज्जु प्रतिस्थापन

मान लीजिए L एक भाषा (कंप्यूटर विज्ञान) है, और मान लीजिए कि Σ इसकी वर्णमाला है। एक 'रज्जु प्रतिस्थापन' या बस एक 'प्रतिस्थापन' एक मैपिंग एफ है जो Σ में वर्णों को भाषाओं में मैप करता है (संभवतः एक अलग वर्णमाला में)। इस प्रकार, उदाहरण के लिए, एक अक्षर a ∈ Σ दिया गया है, तो किसी के पास f(a)=L है_a जहां एल_a ⊆ Δक्लीन स्टार|^* कुछ भाषा है जिसकी वर्णमाला Δ है। इस मैपिंग को स्ट्रिंग्स तक बढ़ाया जा सकता है

f(ε)=ε

खाली रज्जु ε के लिए, और

f(sa)=f(s)f(a)

रज्जु s ∈ L और वर्ण a ∈ Σ के लिए। रज्जु प्रतिस्थापन को संपूर्ण भाषाओं तक बढ़ाया जा सकता है

$f(L)=\bigcup _{s\in L}f(s)$

नियमित भाषाएँ रज्जु प्रतिस्थापन के अंतर्गत बंद हैं। अर्थात्, यदि किसी नियमित भाषा की वर्णमाला में प्रत्येक वर्ण को किसी अन्य नियमित भाषा द्वारा प्रतिस्थापित किया जाता है, तो परिणाम अभी भी एक नियमित भाषा ही है। इसी प्रकार, संदर्भ-मुक्त भाषाएँ रज्जु प्रतिस्थापन के अंतर्गत बंद हो जाती हैं। एक सरल उदाहरण रूपांतरण एफ है_uc(.) को अपरकेस में, जिसे परिभाषित किया जा सकता है जैसे निम्नलिखित नुसार:

character	mapped to language	remark
x	fuc(x)
‹a›	{ ‹A› }	map lowercase char to corresponding uppercase char
‹A›	{ ‹A› }	map uppercase char to itself
‹ß›	{ ‹SS› }	no uppercase char available, map to two-char string
‹0›	{ ε }	map digit to empty string
‹!›	{ }	forbid punctuation, map to empty language
...		similar for other chars

एफ के विस्तार के लिए_uc स्ट्रिंग्स के लिए, हमारे पास उदा.

• एफ_uc(‹सड़क›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹सड़क›},
• एफ_uc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, और
• एफ_uc(‹जाओ!›) = {‹जी›} ⋅ {‹ओ›} ⋅ {} = {}.

एफ के विस्तार के लिए_uc भाषाओं के लिए, हमारे पास उदा.

• एफ_uc({ ‹सड़क›, ‹u2›, ‹जाओ!› }) = { ‹सड़क› } ∪ { ‹U› } ∪ { } = { ‹सड़क›, ‹U› }.

रज्जु समरूपता

एक रज्जु होमोमोर्फिज्म (अक्सर औपचारिक भाषा सिद्धांत में औपचारिक भाषा सिद्धांत में होमोमोर्फिज्म#होमोमोर्फिज्म और ई-मुक्त होमोमोर्फिज्म के रूप में संदर्भित) एक रज्जु प्रतिस्थापन है जैसे कि प्रत्येक वर्ण को एक रज्जु द्वारा प्रतिस्थापित किया जाता है। वह है, $f(a)=s$, कहाँ $s$ प्रत्येक वर्ण के लिए एक रज्जु है $a$. रज्जु होमोमोर्फिज्म मुक्त मोनोइड मुफ़्त मोनॉयड आकारिकी हैं, जो खाली रज्जु और रज्जु संयोजन के बाइनरी ऑपरेशन को संरक्षित करते हैं। एक भाषा दी गई $L$, सेट $f(L)$ की समरूपी छवि कहलाती है $L$. एक रज्जु की व्युत्क्रम समरूपी छवि $s$ परिभाषित किया जाता है

$f^{-1}(s)=\{w|f(w)=s\}$ जबकि किसी भाषा की व्युत्क्रम समरूपी छवि $L$ परिभाषित किया जाता है

$f^{-1}(L)=\{s|f(s)\in L\}$ सामान्य रूप में, $f(f^{-1}(L))\neq L$, जबकि एक के पास है

$f(f^{-1}(L))\subseteq L$ और

$L\subseteq f^{-1}(f(L))$ किसी भी भाषा के लिए $L$.

नियमित भाषाओं का वर्ग समरूपता और व्युत्क्रम समरूपता के अंतर्गत बंद है। इसी प्रकार, संदर्भ-मुक्त भाषाएँ समरूपता के अंतर्गत बंद हैं और व्युत्क्रम समरूपताएँ। एक रज्जु समरूपता को ε-मुक्त (या ई-मुक्त) कहा जाता है यदि $f(a)\neq \varepsilon$ वर्णमाला में सभी के लिए $\Sigma$. सरल एकल-अक्षर प्रतिस्थापन सिफर (ε-मुक्त) रज्जु समरूपता के उदाहरण हैं।

एक उदाहरण रज्जु समरूपता जी_uc #स्ट्रिंग_प्रतिस्थापन प्रतिस्थापन के समान परिभाषित करके भी प्राप्त किया जा सकता है: जी_uc(‹ए›) = ‹ए›, ..., जी_uc(‹0›) = ε, लेकिन g देना_uc विराम चिन्हों पर अपरिभाषित रहें। व्युत्क्रम समरूपी छवियों के उदाहरण हैं

• जी_uc⁻¹({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, चूँकि g_uc(‹sss›) = जी_uc(‹sß›) = जी_uc(‹ßs›) = ‹SSS›, और
• जी_uc⁻¹({ ‹A›, ‹bb› }) = { ‹a› }, चूँकि g_uc(‹a›) = ‹A›, जबकि ‹bb› तक g द्वारा नहीं पहुंचा जा सकता_uc.

बाद वाली भाषा के लिए, जी_uc(जी_uc⁻¹({ ‹A›, ‹bb› })) = g_uc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. समरूपता जी_uc यह ε-मुक्त नहीं है, क्योंकि यह उदाहरण के लिए मैप करता है। ‹0› से ε.

एक बहुत ही सरल रज्जु होमोमोर्फिज्म उदाहरण जो प्रत्येक वर्ण को केवल एक वर्ण में मैप करता है वह EBCDIC-एन्कोडेड रज्जु को ASCII में परिवर्तित करना है।

रज्जु प्रक्षेपण

यदि s एक रज्जु है, और $\Sigma$ एक वर्णमाला है, एस का रज्जु प्रक्षेपण वह रज्जु है जो उन सभी वर्णों को हटाकर परिणामित होता है जो इसमें नहीं हैं $\Sigma$. ऐसा लिखा है $\pi _{\Sigma }(s)\,$. इसे औपचारिक रूप से दाहिनी ओर से वर्णों को हटाकर परिभाषित किया गया है:

$\pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}$

यहाँ $\varepsilon$ खाली रज्जु को दर्शाता है. एक रज्जु का प्रक्षेपण मूलतः संबंधपरक बीजगणित में प्रक्षेपण के समान है।

किसी भाषा के प्रक्षेपण के लिए रज्जु प्रक्षेपण को बढ़ावा दिया जा सकता है। एक औपचारिक भाषा एल दी गई है, इसका प्रक्षेपण द्वारा दिया गया है

$\pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}$

दायां और बायां भागफल

एक रज्जु s से a वर्ण का दायां भागफल, दाहिनी ओर से रज्जु s में वर्ण a का कटाव है। इसे इस प्रकार दर्शाया गया है $s/a$. यदि रज्जु में दाहिनी ओर a नहीं है, तो परिणाम खाली रज्जु है। इस प्रकार:

$(sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}$

खाली रज्जु का भागफल लिया जा सकता है:

$\varepsilon /a=\varepsilon$

इसी प्रकार, एक उपसमुच्चय दिया गया है $S\subset M$ एक मोनॉयड का $M$, कोई भागफल उपसमुच्चय को इस प्रकार परिभाषित कर सकता है

$S/a=\{s\in M\ \vert \ sa\in S\}$

बाएँ भागफल को समान रूप से परिभाषित किया जा सकता है, जिसमें संचालन एक रज्जु के बाईं ओर होता है।

हॉपक्रॉफ्ट और उल्मैन (1979) भागफल एल को परिभाषित करते हैं₁/एल₂ भाषाओं में से एल₁ और मैं₂ उसी वर्णमाला के ऊपर L₁/L₂ = { s | ∃t∈L₂. st∈L₁ }. यह उपरोक्त परिभाषा का सामान्यीकरण नहीं है, क्योंकि, एक रज्जु एस और अलग-अलग वर्णों ए, बी के लिए, हॉपक्रॉफ्ट और उलमैन की परिभाषा का तात्पर्य है उपज {}, इसके बजाय { ε }.

एक सिंगलटन भाषा L का बायाँ भागफल (जब हॉपक्रॉफ्ट और उलमैन 1979 के समान परिभाषित किया गया)₁ और एक मनमानी भाषा एल₂ ब्रज़ोज़ोस्की व्युत्पन्न के रूप में जाना जाता है; यदि एल₂ इसे नियमित अभिव्यक्ति द्वारा दर्शाया जाता है, इसलिए बायां भागफल भी हो सकता है।

वाक्यात्मक संबंध

किसी उपसमुच्चय का सही भागफल $S\subset M$ एक मोनॉयड का $M$ एक तुल्यता संबंध को परिभाषित करता है, जिसे एस का सही वाक्यात्मक संबंध कहा जाता है। यह द्वारा दिया गया है

$\sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}$

संबंध स्पष्ट रूप से परिमित सूचकांक का है (समतुल्य वर्गों की एक सीमित संख्या है) यदि और केवल यदि पारिवारिक सही भागफल परिमित है; वह है, यदि

$\{S/m\ \vert \ m\in M\}$

परिमित है. इस मामले में कि एम कुछ वर्णमाला पर शब्दों का मोनोइड है, एस तब एक नियमित भाषा है, यानी, एक ऐसी भाषा जिसे एक सीमित राज्य ऑटोमेटन द्वारा पहचाना जा सकता है। वाक्यात्मक मोनॉयड पर लेख में इस पर अधिक विस्तार से चर्चा की गई है।

सही रद्दीकरण

एक रज्जु एस से ए अक्षर का सही रद्दीकरण दाईं ओर से शुरू होने वाली रज्जु एस में अक्षर ए की पहली घटना को हटाना है। इसे इस प्रकार दर्शाया गया है $s\div a$ और इसे पुनरावर्ती रूप से परिभाषित किया गया है

$(sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}$

खाली रज्जु हमेशा रद्द करने योग्य होती है:

$\varepsilon \div a=\varepsilon$

स्पष्ट रूप से, सही रद्दीकरण और प्रक्षेपण क्रमविनिमेय संपत्ति:

$\pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)$

उपसर्ग

एक रज्जु के उपसर्ग किसी दी गई भाषा के संबंध में, एक रज्जु के सभी उपसर्गों (कंप्यूटर विज्ञान) का सेट है:

$\operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}$

कहाँ $s\in L$.

किसी भाषा का उपसर्ग समापन है

$\operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}$

उदाहरण:
$L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}$ किसी भाषा को उपसर्ग बंद यदि कहा जाता है $\operatorname {Pref} (L)=L$.

उपसर्ग बंद करने वाला ऑपरेटर निष्क्रिय है:

$\operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)$

उपसर्ग संबंध एक द्विआधारी संबंध है $\sqsubseteq$ ऐसा है कि $s\sqsubseteq t$ अगर और केवल अगर $s\in \operatorname {Pref} _{L}(t)$. यह संबंध उपसर्ग क्रम का एक विशेष उदाहरण है।

यह भी देखें

• प्रोग्रामिंग भाषाओं की तुलना (रज्जु फलनो)
• लेवी की लेम्मा
• रज्जु (कंप्यूटर विज्ञान)#औपचारिक सिद्धांत|रज्जु (कंप्यूटर विज्ञान) - स्ट्रिंग्स पर अधिक बुनियादी संचालन की परिभाषा और कार्यान्वयन

संदर्भ

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages and Computation. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001. (See chapter 3.)