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

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

रज्जु और भाषाएँ

एक रज्जु वर्णों का एक सीमित अनुक्रम है। रिक्त रज्जु को $\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\cdot t\mid s\in S\land t\in T\}$ के लिय संश्रृंखलन $S\cdot T$ को $S$ से किसी भी रज्जु और $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$ उन सभी वर्णों का समुच्चय है जो औपचारिक रूप से ,$\operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)$, $S$ के किसी भी रज्जु में होते हैं।

उदाहरण के लिए, समुच्चय $\{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}$ रज्जु $\langle cacao\rangle$ की वर्णमाला है, और उपरोक्त $D$ उपरोक्त भाषा $D\cdot D\cdot D$ के साथ-साथ सभी दशमलव संख्याओं की भाषा की वर्णमाला है।

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

मान कि L एक भाषा है, और Σ इसकी वर्णमाला है। एक 'रज्जु प्रतिस्थापन' या केवल एक 'प्रतिस्थापन' एक प्रतिचित्रण f है जो Σ में वर्णों को भाषाओं (संभवतः एक अलग वर्णमाला में) में प्रतिचित्रित करता है। इस प्रकार, उदाहरण के लिए, एक अक्षर a ∈ Σ दिया गया है, तो किसी के पास f(a)=L_a है जहां L_a ⊆ Δ^* विशिष्ट भाषा है जिसकी वर्णमाला Δ है। इस प्रतिचित्रण को रिक्त रज्जु ε के लिए

f(ε)=ε

के रूप में रज्जु तक बढ़ाया जा सकता है, और रज्जु s ∈ L और वर्ण a ∈ Σ के लिए

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

तक बढ़ाया जा सकता है। रज्जु प्रतिस्थापन को संपूर्ण भाषाओं में

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

के रूप में विस्तारित किया जा सकता है, नियमित भाषाएँ रज्जु प्रतिस्थापन के अंतर्गत संवृत हैं। अर्थात्, यदि किसी नियमित भाषा की वर्णमाला में प्रत्येक वर्ण को किसी अन्य नियमित भाषा द्वारा प्रतिस्थापित किया जाता है, तो परिणाम अभी भी एक नियमित भाषा ही है। इसी प्रकार, संदर्भ-मुक्त भाषाएं रज्जु प्रतिस्थापन के अंतर्गत संवृत हो जाती हैं।

एक सरल उदाहरण f_uc(.) को बड़े अक्षर में रूपांतरित करना है, जिसे परिभाषित किया जा सकता है तथा निम्नलिखित अनुसार लिखा जा सकता है,

वर्ण	भाषा में मानचित्रित	टिप्पणी
x	fuc(x)
‹a›	{ ‹A› }	छोटे अक्षर वर्ण को संबंधित बड़े अक्षर वर्ण में मानचित्रित करें
‹A›	{ ‹A› }	बड़े अक्षर वर्ण को स्वयं मानचित्रित करें
‹ß›	{ ‹SS› }	कोई बड़े अक्षर वर्ण उपलब्ध नहीं है, दो-वर्ण रज्जु पर मानचित्रित करें
‹0›	{ ε }	अंक को रिक्त रज्जु में मानचित्रित करें
‹!›	{ }	विराम चिह्न वर्जित करें, रिक्त भाषा का मानचित्र बनाएं
...		अन्य वर्णों के लिए समान

f_uc को रज्जु तक विस्तारित करने के लिए, हमारे पास निम्नलिखित उदा है,

• f_uc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹एसटीआरएएसएसई›},
• f_uc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, और
• f_uc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

भाषाओं में f_uc के विस्तार के लिए, हमारे पास निम्नलिखित उदा है,

• f_uc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹एसटीआरएएसएसई› } ∪ { ‹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$, जबकि किसी भाषा $L$ के लिए

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

$L\subseteq f^{-1}(f(L))$ होते हैं।

नियमित भाषाओं का वर्ग समरूपता और व्युत्क्रम समरूपता के अंतर्गत संवृत है। इसी प्रकार, संदर्भ-मुक्त भाषाएँ समरूपता और व्युत्क्रम समरूपता के अंतर्गत संवृत हैं।

एक रज्जु समरूपता को ε-मुक्त (या e-मुक्त) कहा जाता है यदि वर्णमाला $\Sigma$ में सभी a के लिए $f(a)\neq \varepsilon$ हो। सरल एकल-अक्षर प्रतिस्थापन संकेताक्षर (ε-मुक्त) रज्जु समरूपता के उदाहरण हैं।

उपरोक्त प्रतिस्थापन के समान परिभाषित करके एक उदाहरण रज्जु समरूपता g_ucभी प्राप्त किया जा सकता है, g_uc(‹a›) = ‹a›, ..., जी_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.)