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

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

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

एक स्ट्रिंग वर्णों का एक सीमित अनुक्रम है। खाली स्ट्रिंग को इसके द्वारा निरूपित किया जाता है $\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.)