स्ट्रिंग ऑपरेशन: Difference between revisions

From Vigyanwiki
No edit summary
 
(21 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, [[औपचारिक भाषा सिद्धांत]] के क्षेत्र में, विभिन्न प्रकार के [[स्ट्रिंग फ़ंक्शंस|स्ट्रिंग फलनो]] का लगातार उपयोग किया जाता है, हालाँकि, उपयोग किया गया नोटेशन [[कंप्यूटर प्रोग्रामिंग]] के लिए उपयोग किए जाने वाले नोटेशन से भिन्न है, और सैद्धांतिक क्षेत्र में आमतौर पर उपयोग किए जाने वाले कुछ फ़ंक्शन प्रोग्रामिंग करते समय शायद ही कभी उपयोग किए जाते हैं। यह आलेख इनमें से कुछ बुनियादी शब्दों को परिभाषित करता है।
[[कंप्यूटर विज्ञान]] में, [[औपचारिक भाषा सिद्धांत]] के क्षेत्र में, विभिन्न प्रकार के [[स्ट्रिंग फ़ंक्शंस|रज्जु फलनो]] का लगातार उपयोग किया जाता है, हालाँकि, उपयोग किया गया संकेतन [[कंप्यूटर प्रोग्रामिंग]] के लिए उपयोग किए जाने वाले संकेतन से भिन्न है, और सैद्धांतिक क्षेत्र में आमतौर पर उपयोग किए जाने वाले कुछ फलन प्रोग्रामिंग करते समय शायद ही कभी उपयोग किए जाते हैं। यह आलेख इनमें से कुछ मूल शब्दों को परिभाषित करता है।


==स्ट्रिंग्स और भाषाएँ==
==रज्जु और भाषाएँ==
एक स्ट्रिंग वर्णों का एक सीमित अनुक्रम है।
एक रज्जु वर्णों का एक सीमित अनुक्रम है। [[रिक्त रज्जु]] को <math>\varepsilon</math> के द्वारा निरूपित किया जाता है। दो रज्जु <math>s</math> और <math>t</math> के संश्रृंखलन को <math>s \cdot t</math> या <math>s t</math> द्वारा दर्शाया जाता है। रिक्त रज्जु के साथ संश्रृंखलन करने से कोई अंतर नहीं पड़ता, <math>s \cdot \varepsilon = s = \varepsilon \cdot s</math>। रज्जु का संश्रृंखलन साहचर्य है, <math>s \cdot (t \cdot u) = (s \cdot t) \cdot u</math>
[[खाली स्ट्रिंग]] को इसके द्वारा निरूपित किया जाता है <math>\varepsilon</math>.
दो तारों का संयोजन <math>s</math> और <math>t</math> द्वारा निरूपित किया जाता है <math>s \cdot t</math>, या इससे छोटा <math>s t</math>.
खाली स्ट्रिंग के साथ संयोजन करने से कोई फर्क नहीं पड़ता: <math>s \cdot \varepsilon = s = \varepsilon \cdot s</math>.
तारों का संयोजन साहचर्य है: <math>s \cdot (t \cdot u) = (s \cdot t) \cdot u</math>.


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


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


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


उदाहरण के लिए, संक्षिप्त करना <math>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 \}</math>, सभी तीन अंकों वाली दशमलव संख्याओं का समुच्चय इस प्रकार प्राप्त होता है <math>D \cdot D \cdot D</math>. मनमानी लंबाई की सभी दशमलव संख्याओं का सेट एक अनंत भाषा के लिए एक उदाहरण है।
उदाहरण के लिए, <math>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 \}</math> को संक्षिप्त करने पर सभी तीन अंकों की दशमलव संख्याओं का समुच्चय <math>D \cdot D \cdot D</math> के रूप में प्राप्त होता है। यादृच्छिक लंबाई की सभी दशमलव संख्याओं का समुच्चय एक अनंत भाषा के लिए एक उदाहरण है।


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


:<math>\operatorname{Alph}(s)</math>
:<math>\operatorname{Alph}(s)</math>
किसी भाषा की वर्णमाला <math>S</math> किसी भी स्ट्रिंग में आने वाले सभी वर्णों का समूह है <math>S</math>, औपचारिक रूप से:
द्वारा दर्शायी जाती है। किसी भाषा की वर्णमाला <math>S</math> उन सभी वर्णों का समुच्चय है जो औपचारिक रूप से ,<math>\operatorname{Alph}(S) = \bigcup_{s \in S} \operatorname{Alph}(s)</math>, <math>S</math> के किसी भी रज्जु में होते हैं।
<math>\operatorname{Alph}(S) = \bigcup_{s \in S} \operatorname{Alph}(s)</math>.


उदाहरण के लिए, सेट <math>\{\langle a \rangle,\langle c \rangle,\langle o \rangle\}</math> स्ट्रिंग का वर्णमाला है <math>\langle cacao \rangle</math>,
उदाहरण के लिए, समुच्चय <math>\{\langle a \rangle,\langle c \rangle,\langle o \rangle\}</math> रज्जु <math>\langle cacao \rangle</math> की वर्णमाला है, और [[उपरोक्त]] <math>D</math> [[उपरोक्त]] भाषा <math>D \cdot D \cdot D</math> के साथ-साथ सभी दशमलव संख्याओं की भाषा की वर्णमाला है।
और #स्ट्रिंग्स_और_भाषाएँ <math>D</math> #स्ट्रिंग्स_एंड_लैंग्वेजेज भाषा की वर्णमाला है <math>D \cdot D \cdot D</math> साथ ही सभी दशमलव संख्याओं की भाषा भी।


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


:f(ε)=ε
:f(ε)=ε


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


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


स्ट्रिंग s ∈ L और वर्ण a ∈ Σ के लिए। स्ट्रिंग प्रतिस्थापन को संपूर्ण भाषाओं तक बढ़ाया जा सकता है <ref>Hopcroft, Ullman (1979), Sect.3.2, p.60</ref>
तक बढ़ाया जा सकता है। रज्जु प्रतिस्थापन को संपूर्ण भाषाओं में <ref>Hopcroft, Ullman (1979), Sect.3.2, p.60</ref>
:<math>f(L)=\bigcup_{s\in L} f(s)</math>
:<math>f(L)=\bigcup_{s\in L} f(s)</math>
[[नियमित भाषा]]एँ स्ट्रिंग प्रतिस्थापन के अंतर्गत बंद हैं। अर्थात्, यदि किसी नियमित भाषा की वर्णमाला में प्रत्येक वर्ण को किसी अन्य नियमित भाषा द्वारा प्रतिस्थापित किया जाता है, तो परिणाम अभी भी एक नियमित भाषा ही है।<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60</ref>
के रूप में विस्तारित किया जा सकता है, [[नियमित भाषा|नियमित भाषाएँ]] रज्जु प्रतिस्थापन के अंतर्गत संवृत हैं। अर्थात्, यदि किसी नियमित भाषा की वर्णमाला में प्रत्येक वर्ण को किसी अन्य नियमित भाषा द्वारा प्रतिस्थापित किया जाता है, तो परिणाम अभी भी एक नियमित भाषा ही है।<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60</ref> इसी प्रकार, [[संदर्भ-मुक्त भाषा|संदर्भ-मुक्त भाषाएं]] रज्जु प्रतिस्थापन के अंतर्गत संवृत हो जाती हैं।<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131</ref><ref group="note">Although every regular language is also context-free, the previous theorem is not implied by the current one, since the former yields a shaper result for regular languages.</ref>
इसी प्रकार, [[संदर्भ-मुक्त भाषा]]एँ स्ट्रिंग प्रतिस्थापन के अंतर्गत बंद हो जाती हैं।<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131</ref><ref group="note">Although every regular language is also context-free, the previous theorem is not implied by the current one, since the former yields a shaper result for regular languages.</ref>
 
एक सरल उदाहरण रूपांतरण एफ है<sub>uc</sub>(.) को अपरकेस में, जिसे परिभाषित किया जा सकता है जैसे निम्नलिखित नुसार:
एक सरल उदाहरण f<sub>uc</sub>(.) को बड़े अक्षर में रूपांतरित करना है, जिसे परिभाषित किया जा सकता है तथा निम्नलिखित अनुसार लिखा जा सकता है,


{| class="wikitable"
{| class="wikitable"
|-
|-
! character !! mapped to language !! remark
! वर्ण !! भाषा में मानचित्रित !! टिप्पणी
|-
|-
! ''x'' !! ''f''<sub>uc</sub>(''x'') !!
! ''x'' !! ''f''<sub>uc</sub>(''x'') !!
|-
|-
| ‹''a''› || { ‹''A''› } || map lowercase char to corresponding uppercase char
| ‹''a''› || { ‹''A''› } || छोटे अक्षर वर्ण को संबंधित बड़े अक्षर वर्ण में मानचित्रित करें
|-
|-
| ‹''A''› || { ‹''A''› } || map uppercase char to itself
| ‹''A''› || { ‹''A''› } || बड़े अक्षर वर्ण को स्वयं मानचित्रित करें
|-
|-
| ‹''ß''› || { ‹''SS''› } || no uppercase char available, map to two-char string
| ‹''ß''› || { ‹''SS''› } || कोई बड़े अक्षर वर्ण उपलब्ध नहीं है, दो-वर्ण रज्जु पर मानचित्रित करें
|-
|-
| ‹0› || { ε } || map digit to empty string
| ‹0› || { ε } || अंक को रिक्त रज्जु में मानचित्रित करें
|-
|-
| ‹!› || { } || forbid punctuation, map to empty language
| ‹!› || { } || विराम चिह्न वर्जित करें, रिक्त भाषा का मानचित्र बनाएं
|-
|-
| ... || || similar for other chars
| ... || || अन्य वर्णों के लिए समान
|}
|}
एफ के विस्तार के लिए<sub>uc</sub> स्ट्रिंग्स के लिए, हमारे पास उदा.
f<sub>uc</sub> को रज्जु तक विस्तारित करने के लिए, हमारे पास निम्नलिखित उदा है,
* एफ<sub>uc</sub>(‹सड़क›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹सड़क›},
* f<sub>uc</sub>(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹एसटीआरएएसएसई›},
* एफ<sub>uc</sub>(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, और
* f<sub>uc</sub>(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, और
* एफ<sub>uc</sub>(‹जाओ!›) = {‹जी›} ⋅ {‹ओ›} ⋅ {} = {}.
* f<sub>uc</sub>(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.
एफ के विस्तार के लिए<sub>uc</sub> भाषाओं के लिए, हमारे पास उदा.
भाषाओं में f<sub>uc</sub> के विस्तार के लिए, हमारे पास निम्नलिखित उदा है,
* एफ<sub>uc</sub>({ ‹सड़क›, ‹u2›, ‹जाओ!› }) = { ‹सड़क› } ∪ { ‹U› } ∪ { } = { ‹सड़क›, ‹U› }.
* f<sub>uc</sub>({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹एसटीआरएएसएसई› } ∪ { ‹U› } ∪ { } = { ‹एसटीआरएएसएसई›, ‹U› }
 
==रज्जु समरूपता==
एक '''रज्जु समरूपता'''  (प्रायः [[औपचारिक भाषा सिद्धांत]] में इसे केवल समरूपता के रूप में संदर्भित किया जाता है) एक रज्जु प्रतिस्थापन है जैसे कि प्रत्येक वर्ण को एक रज्जु द्वारा प्रतिस्थापित किया जाता है। अर्थात्, <math>f(a)=s</math>, जहां <math>s</math> प्रत्येक वर्ण <math>a</math> के लिए एक रज्जु है।<ref group="note" name="singleton sets">Strictly formally, a homomorphism yields a language consisting of just one string, i.e. <math>f(a) = {s}</math>.</ref><ref>Hopcroft, Ullman (1979), Sect.3.2, p.60-61</ref>
 
रज्जु समरूपता [[मुक्त एकाभ]] पर [[मुफ़्त मोनॉयड|मुफ़्त एकाभ]]आकारिकी हैं, जो रिक्त रज्जु और [[स्ट्रिंग संयोजन|रज्जु संश्रृंखलन]] के [[बाइनरी ऑपरेशन|द्विआधारी संक्रिया]] को संरक्षित करते हैं। किसी भाषा <math>L</math> को देखते हुए, समुच्चय <math>f(L)</math> को <math>L</math> का '''समरूपी प्रतिबिम्ब''' कहा जाता है। एक रज्जु <math>s</math> का व्युत्क्रम समरूपी प्रतिबिम्ब को


==स्ट्रिंग समरूपता==
<math>f^{-1}(s) = \{ w | f(w) = s \}</math> के रूप में परिभाषित किया गया है, जबकि किसी भाषा <math>L</math> के व्युत्क्रम समरूपी प्रतिबिम्ब को
एक स्ट्रिंग होमोमोर्फिज्म (अक्सर औपचारिक भाषा सिद्धांत में औपचारिक भाषा सिद्धांत में होमोमोर्फिज्म#होमोमोर्फिज्म और ई-मुक्त होमोमोर्फिज्म के रूप में संदर्भित) एक स्ट्रिंग प्रतिस्थापन है जैसे कि प्रत्येक वर्ण को एक स्ट्रिंग द्वारा प्रतिस्थापित किया जाता है। वह है, <math>f(a)=s</math>, कहाँ <math>s</math> प्रत्येक वर्ण के लिए एक स्ट्रिंग है <math>a</math>.<ref group="note" name="singleton sets">Strictly formally, a homomorphism yields a language consisting of just one string, i.e. <math>f(a) = {s}</math>.</ref><ref>Hopcroft, Ullman (1979), Sect.3.2, p.60-61</ref>
स्ट्रिंग होमोमोर्फिज्म मुक्त मोनोइड [[मुफ़्त मोनॉयड]] आकारिकी हैं, जो खाली स्ट्रिंग और [[स्ट्रिंग संयोजन]] के [[बाइनरी ऑपरेशन]] को संरक्षित करते हैं। एक भाषा दी गई <math>L</math>, सेट <math>f(L)</math> की समरूपी छवि कहलाती है <math>L</math>. एक स्ट्रिंग की व्युत्क्रम समरूपी छवि <math>s</math> परिभाषित किया जाता है


<math>f^{-1}(s) = \{ w | f(w) = s \}</math>
<math>f^{-1}(L) = \{ s | f(s) \in L \}</math> के रूप में परिभाषित किया जाता है, सामान्य तौर पर, <math>f(f^{-1}(L)) \neq L</math>, जबकि किसी भाषा <math>L</math> के लिए
जबकि किसी भाषा की व्युत्क्रम समरूपी छवि <math>L</math> परिभाषित किया जाता है


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


<math>f(f^{-1}(L)) \subseteq L</math>
<math>L \subseteq f^{-1}(f(L))</math> होते हैं।
और


<math>L \subseteq f^{-1}(f(L))</math>
नियमित भाषाओं का वर्ग समरूपता और व्युत्क्रम समरूपता के अंतर्गत संवृत है।<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61</ref> इसी प्रकार, संदर्भ-मुक्त भाषाएँ समरूपता <ref group="note">This follows from the [[#String substitution|above-mentioned]] closure under arbitrary substitutions.</ref> और व्युत्क्रम समरूपता के अंतर्गत संवृत हैं।<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132</ref>
किसी भी भाषा के लिए <math>L</math>.


नियमित भाषाओं का वर्ग समरूपता और व्युत्क्रम समरूपता के अंतर्गत बंद है।<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61</ref> इसी प्रकार, संदर्भ-मुक्त भाषाएँ समरूपता के अंतर्गत बंद हैं<ref group="note">This follows from the [[#String substitution|above-mentioned]] closure under arbitrary substitutions.</ref> और व्युत्क्रम समरूपताएँ।<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132</ref>
एक रज्जु समरूपता को ε-मुक्त (या e-मुक्त) कहा जाता है यदि वर्णमाला <math>\Sigma</math> में सभी a के लिए <math>f(a) \neq \varepsilon</math> हो। सरल एकल-अक्षर [[प्रतिस्थापन सिफर|प्रतिस्थापन संकेताक्षर]] (ε-मुक्त) रज्जु समरूपता के उदाहरण हैं।
एक स्ट्रिंग समरूपता को ε-मुक्त (या -मुक्त) कहा जाता है यदि <math>f(a) \neq \varepsilon</math> वर्णमाला में सभी के लिए <math>\Sigma</math>. सरल एकल-अक्षर [[प्रतिस्थापन सिफर]] (ε-मुक्त) स्ट्रिंग समरूपता के उदाहरण हैं।


एक उदाहरण स्ट्रिंग समरूपता जी<sub>uc</sub> #स्ट्रिंग_प्रतिस्थापन प्रतिस्थापन के समान परिभाषित करके भी प्राप्त किया जा सकता है: जी<sub>uc</sub>(‹ए›) = ‹ए›, ..., जी<sub>uc</sub>(‹0›) = ε, लेकिन g देना<sub>uc</sub> विराम चिन्हों पर अपरिभाषित रहें।
उपरोक्त प्रतिस्थापन के समान परिभाषित करके एक उदाहरण रज्जु समरूपता g<sub>uc</sub>भी प्राप्त किया जा सकता है, g<sub>uc</sub>(‹a›) = ‹A›, ..., g<sub>uc</sub>(‹0›) = ε, लेकिन लेकिन विराम चिन्हों पर g<sub>uc</sub> को अपरिभाषित रहने देना। व्युत्क्रम समरूपी प्रतिबिम्बो के उदाहरण हैं
<!---omitted, since sloppy notation, anyway, see above---
* g<sub>uc</sub><sup>−1</sup>({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, क्योंकि g<sub>uc</sub>(‹sss›) = g<sub>uc</sub>(‹sß›) = g<sub>uc</sub>(‹ßs›) = ‹SSS›, और
Besides this restriction of its input domain, ''g''<sub>uc</sub> differs from ''f''<sub>uc</sub> by returning strings,<ref group=note name="singleton sets"/> while the latter returned singleton sets of strings.
*g<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› }) = { ‹a› }, क्योंकि g<sub>uc</sub>(‹a›) = ‹A›, जबकि ‹bb› तक g<sub>uc</sub> द्वारा नहीं पहुंचा जा सकता।
--->
बाद वाली भाषा के लिए, g<sub>uc</sub>(g<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› })) = g<sub>uc</sub>({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }समरूपता g<sub>uc</sub> ε-मुक्त नहीं है, क्योंकि यह उदाहरण के लिए ‹0› से ε तक मानचित्रित करता है।
व्युत्क्रम समरूपी छवियों के उदाहरण हैं
* जी<sub>uc</sub><sup>−1</sup>({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, चूँकि g<sub>uc</sub>(‹sss›) = जी<sub>uc</sub>(‹sß›) = जी<sub>uc</sub>(‹ßs›) = ‹SSS›, और
*जी<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› }) = { ‹a› }, चूँकि g<sub>uc</sub>(‹a›) = ‹A›, जबकि ‹bb› तक g द्वारा नहीं पहुंचा जा सकता<sub>uc</sub>.
बाद वाली भाषा के लिए, जी<sub>uc</sub>(जी<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› })) = g<sub>uc</sub>({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }.
समरूपता जी<sub>uc</sub> यह ε-मुक्त नहीं है, क्योंकि यह उदाहरण के लिए मैप करता है। ‹0› से ε.


एक बहुत ही सरल स्ट्रिंग होमोमोर्फिज्म उदाहरण जो प्रत्येक वर्ण को केवल एक वर्ण में मैप करता है वह [[EBCDIC]]-एन्कोडेड स्ट्रिंग को [[ASCII]] में परिवर्तित करना है।
एक बहुत ही सरल रज्जु समरूपता उदाहरण जो प्रत्येक वर्ण को केवल एक वर्ण में मानचित्रित करता है तथा वह [[EBCDIC|इबीसीडीआईसी]]-कूटबद्‍ध रज्जु को [[ASCII|एएससीआईआई]] में परिवर्तित करता है।


==स्ट्रिंग प्रक्षेपण==
==रज्जु प्रक्षेपण==
यदि s एक स्ट्रिंग है, और <math>\Sigma</math> एक वर्णमाला है, ''एस'' का स्ट्रिंग प्रक्षेपण वह स्ट्रिंग है जो उन सभी वर्णों को हटाकर परिणामित होता है जो इसमें नहीं हैं <math>\Sigma</math>. ऐसा लिखा है <math>\pi_\Sigma(s)\,</math>. इसे औपचारिक रूप से दाहिनी ओर से वर्णों को हटाकर परिभाषित किया गया है:
यदि s एक रज्जु है, और <math>\Sigma</math> एक वर्णमाला है, ''तो'' s का '''रज्जु प्रक्षेपण''' वह रज्जु है जिसके परिणामस्वरूप उन सभी वर्णों को हटा दिया जाता है जो <math>\Sigma</math> में नहीं हैं।`इसे  <math>\pi_\Sigma(s)\,</math>के रूप में लिखा जाता है। इसे औपचारिक रूप से दाहिनी ओर से वर्णों को हटाकर परिभाषित किया गया है,


:<math>\pi_\Sigma(s) = \begin{cases}  
:<math>\pi_\Sigma(s) = \begin{cases}  
Line 111: Line 92:
\pi_\Sigma(t)a & \mbox{if } s=ta \mbox{ and } a \in \Sigma   
\pi_\Sigma(t)a & \mbox{if } s=ta \mbox{ and } a \in \Sigma   
\end{cases}</math>
\end{cases}</math>
यहाँ <math>\varepsilon</math> खाली स्ट्रिंग को दर्शाता है. एक स्ट्रिंग का प्रक्षेपण मूलतः [[संबंधपरक बीजगणित में प्रक्षेपण]] के समान है।
यहाँ <math>\varepsilon</math> [[रिक्त रज्जु]] को दर्शाता है। एक रज्जु का प्रक्षेपण मूलतः [[संबंधपरक बीजगणित में प्रक्षेपण]] के समान है।


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


:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s)\ \vert\ s\in L \}</math>{{citation needed|date=August 2017}}
:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s)\ \vert\ s\in L \}</math>
:द्वारा दिया जाता है।


== दायां और बायां भागफल ==
== दायां और बायां भागफल ==
एक स्ट्रिंग ''s'' से ''a'' वर्ण का दायां भागफल, दाहिनी ओर से स्ट्रिंग ''s'' में वर्ण ''a'' का कटाव है। इसे इस प्रकार दर्शाया गया है <math>s/a</math>. यदि स्ट्रिंग में दाहिनी ओर a नहीं है, तो परिणाम खाली स्ट्रिंग है। इस प्रकार:
रज्जु ''s'' से किसी वर्ण ''a'' का दायां भागफल, रज्जु ''s'' में वर्ण ''a'' का दाहिनी ओर से छिन्न है। इसे <math>s/a</math> के रूप में दर्शाया गया है। यदि रज्जु में दाहिनी ओर a नहीं है, तो परिणाम रिक्त रज्जु होगा। इस प्रकार,
<!---This definition deviates from Hopcroft.Ullman.1979, as remarked below. I guess the former doesn't have widespread use, if it has a source at all.--->
: <math>(sa)/ b = \begin{cases}  
: <math>(sa)/ b = \begin{cases}  
s & \mbox{if } a=b \\
s & \mbox{if } a=b \\
\varepsilon & \mbox{if } a \ne b
\varepsilon & \mbox{if } a \ne b
\end{cases}</math>
\end{cases}</math>
खाली स्ट्रिंग का भागफल लिया जा सकता है:
रिक्त रज्जु का भागफल लिया जा सकता है,
: <math>\varepsilon / a = \varepsilon</math>
: <math>\varepsilon / a = \varepsilon</math>
इसी प्रकार, एक उपसमुच्चय दिया गया है <math>S\subset M</math> एक मोनॉयड का <math>M</math>, कोई भागफल उपसमुच्चय को इस प्रकार परिभाषित कर सकता है
इसी प्रकार, एक एकाभ <math>M</math> का उपसमुच्चय <math>S\subset M</math> दिए जाने पर, भागफल उपसमुच्चय को
: <math>S/a=\{s\in M\ \vert\ sa\in S\}</math>
: <math>S/a=\{s\in M\ \vert\ sa\in S\}</math>
बाएँ भागफल को समान रूप से परिभाषित किया जा सकता है, जिसमें संचालन एक स्ट्रिंग के बाईं ओर होता है।{{citation needed|date=August 2017}}
के रूप में परिभाषित किया जा सकता है, '''बाएँ भागफल''' को समान रूप से परिभाषित किया जा सकता है, जिसमें संचालन एक रज्जु के बाईं ओर होता है।
 
हॉपक्रॉफ्ट और उल्मैन (1979) भागफल एल को परिभाषित करते हैं<sub>1</sub>/एल<sub>2</sub> भाषाओं में से एल<sub>1</sub> और मैं<sub>2</sub> उसी वर्णमाला के ऊपर {{nowrap|1=''L''<sub>1</sub>/''L''<sub>2</sub> = {{mset| ''s'' {{!}} ∃''t''∈''L''<sub>2</sub>. ''st''∈''L''<sub>1</sub> }}}}.<ref>Hopcroft, Ullman (1979), Sect.3.2, p.62</ref>
यह उपरोक्त परिभाषा का सामान्यीकरण नहीं है, क्योंकि, एक स्ट्रिंग एस और अलग-अलग वर्णों ए, बी के लिए, हॉपक्रॉफ्ट और उलमैन की परिभाषा का तात्पर्य है {{nowrap||{{mset|''sa''}} / {{mset|''b''}}}} उपज {{mset|}}, इसके बजाय {{mset| ε }}.
 
एक सिंगलटन भाषा L का बायाँ भागफल (जब हॉपक्रॉफ्ट और उलमैन 1979 के समान परिभाषित किया गया)<sub>1</sub> और एक मनमानी भाषा एल<sub>2</sub> [[ब्रज़ोज़ोस्की व्युत्पन्न]] के रूप में जाना जाता है; यदि एल<sub>2</sub> इसे [[ नियमित अभिव्यक्ति ]] द्वारा दर्शाया जाता है, इसलिए बायां भागफल भी हो सकता है।<ref>{{cite journal| author=Janusz A. Brzozowski| authorlink=Janusz Brzozowski (computer scientist)|title=रेगुलर एक्सप्रेशन के व्युत्पन्न| journal=J ACM| year=1964| volume=11| issue=4| pages=481–494| doi=10.1145/321239.321249| s2cid=14126942}}</ref>


हॉपक्रॉफ्ट और उल्मैन (1979) भाषाओं L<sub>1</sub> और L<sub>2</sub> के भागफल L<sub>1</sub>/L<sub>2</sub> को एलL<sub>1</sub> को  {{nowrap|1=''L''<sub>1</sub>/''L''<sub>2</sub> = {{mset| ''s'' {{!}} ∃''t''∈''L''<sub>2</sub>. ''st''∈''L''<sub>1</sub> }}}} के समान वर्णमाला पर परिभाषित करते हैं।<ref>Hopcroft, Ullman (1979), Sect.3.2, p.62</ref> यह उपरोक्त परिभाषा का सामान्यीकरण नहीं है, क्योंकि, एक रज्जु s और अलग-अलग वर्णों a, b के लिए, हॉपक्रॉफ्ट और उलमैन की परिभाषा का तात्पर्य {{mset| ε }} के बजाय अनुवर्ती {{mset|}} है।


एक एकल भाषा L<sub>1</sub> और एक यादृच्छिक भाषा L<sub>2</sub> के बाएँ भागफल (जब हॉपक्रॉफ्ट और उलमैन 1979 के समान परिभाषित किया गया) को [[ब्रज़ोज़ोस्की व्युत्पन्न|ब्रज़ोज़ोस्की अवकलज]] के रूप में जाना जाता है, यदि L<sub>2</sub> को[[ नियमित अभिव्यक्ति ]]द्वारा दर्शाया जाता है, तो बायां भागफल भी हो सकता है।<ref>{{cite journal| author=Janusz A. Brzozowski| authorlink=Janusz Brzozowski (computer scientist)|title=रेगुलर एक्सप्रेशन के व्युत्पन्न| journal=J ACM| year=1964| volume=11| issue=4| pages=481–494| doi=10.1145/321239.321249| s2cid=14126942}}</ref>
==वाक्यात्मक संबंध==
==वाक्यात्मक संबंध==
किसी उपसमुच्चय का सही भागफल <math>S\subset M</math> एक मोनॉयड का <math>M</math> एक तुल्यता संबंध को परिभाषित करता है, जिसे ''एस'' का सही [[वाक्यात्मक संबंध]] कहा जाता है। यह द्वारा दिया गया है
एक एकाभ का <math>M</math> के उपसमुच्चय <math>S\subset M</math> का दायां भागफल एक [[तुल्यता संबंध]] को परिभाषित करता है, जिसे S का सही [[वाक्यात्मक संबंध]] कहा जाता है। यह


:<math>\sim_S \;\,=\, \{(s,t)\in M\times M\ \vert\ S/s = S/t \}</math>
:<math>\sim_S \;\,=\, \{(s,t)\in M\times M\ \vert\ S/s = S/t \}</math>
संबंध स्पष्ट रूप से परिमित सूचकांक का है (समतुल्य वर्गों की एक सीमित संख्या है) यदि और केवल यदि पारिवारिक सही भागफल परिमित है; वह है, यदि
द्वारा दिया गया है, संबंध स्पष्ट रूप से परिमित सूचकांक का है (समतुल्य वर्गों की एक सीमित संख्या है) यदि सामूहिक सही भागफल परिमित है, अर्थात्, यदि


:<math>\{S/m\ \vert\ m\in M\}</math>
:<math>\{S/m\ \vert\ m\in M\}</math>
परिमित है. इस मामले में कि एम कुछ वर्णमाला पर शब्दों का मोनोइड है, एस तब एक नियमित भाषा है, यानी, एक ऐसी भाषा जिसे एक सीमित राज्य ऑटोमेटन द्वारा पहचाना जा सकता है। [[वाक्यात्मक मोनॉयड]] पर लेख में इस पर अधिक विस्तार से चर्चा की गई है।{{citation needed|date=August 2017}}
परिमित है। इस स्थिति में कि M कुछ वर्णमाला पर शब्दों का एकाभ है, S तब एक [[नियमित भाषा]] है, अर्थात्, एक ऐसी भाषा जिसे एक [[परिमित स्थिति स्वचालन]] द्वारा पहचाना जा सकता है। [[वाक्यात्मक मोनॉयड|वाक्यात्मक एकाभ]] पर लेख में इस पर अधिक विस्तार से चर्चा की गई है।


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


:<math>(sa)\div b = \begin{cases}  
:<math>(sa)\div b = \begin{cases}  
Line 152: Line 130:
(s\div b)a & \mbox{if } a \ne b
(s\div b)a & \mbox{if } a \ne b
\end{cases}</math>
\end{cases}</math>
खाली स्ट्रिंग हमेशा रद्द करने योग्य होती है:
के रूप में परिभाषित किया गया है, रिक्त रज्जु हमेशा रद्द करने योग्य होती है,


:<math>\varepsilon \div a = \varepsilon</math>
:<math>\varepsilon \div a = \varepsilon</math>
स्पष्ट रूप से, सही रद्दीकरण और प्रक्षेपण क्रमविनिमेय संपत्ति:
स्पष्ट रूप से, दक्षिण निरस्तीकरण और प्रक्षेपण क्रमविनिमेय आवागमन.


:<math>\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a )</math>{{citation needed|date=August 2017}}
:<math>\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a )</math>


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


:<math>\operatorname{Pref}_L(s) = \{t\ \vert\ s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}</math>
:<math>\operatorname{Pref}_L(s) = \{t\ \vert\ s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}</math>
कहाँ <math>s\in L</math>.
जहाँ <math>s\in L</math> है ।


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


:<math>\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\}</math>
:<math>\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\}</math>है।
उदाहरण: <br />
उदाहरण,<br /><math>L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\}</math> किसी भाषा को उपसर्ग संवृत कहा जाता है यदि <math>\operatorname{Pref} (L) = L</math> हो।
<math>L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\}</math>
किसी भाषा को उपसर्ग बंद यदि कहा जाता है <math>\operatorname{Pref} (L) = L</math>.


उपसर्ग बंद करने वाला ऑपरेटर [[निष्क्रिय]] है:
उपसर्ग संवृत करने वाला संचालक [[निष्क्रिय]] है,


:<math>\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L)</math>
:<math>\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L)</math>
उपसर्ग संबंध एक [[द्विआधारी संबंध]] है <math>\sqsubseteq</math> ऐसा है कि <math>s\sqsubseteq t </math> अगर और केवल अगर <math>s \in \operatorname{Pref}_L(t)</math>. यह संबंध [[उपसर्ग क्रम]] का एक विशेष उदाहरण है।{{citation needed|date=August 2017}}
उपसर्ग संबंध एक [[द्विआधारी संबंध]] है <math>\sqsubseteq</math>उपसर्ग संबंध एक द्विआधारी संबंध <math>s\sqsubseteq t </math> है यदि  <math>s \in \operatorname{Pref}_L(t)</math> है। यह संबंध [[उपसर्ग क्रम]] का एक विशेष उदाहरण है।


==यह भी देखें==
==यह भी देखें==
* [[प्रोग्रामिंग भाषाओं की तुलना (स्ट्रिंग फ़ंक्शंस)|प्रोग्रामिंग भाषाओं की तुलना (स्ट्रिंग फलनो)]]
* [[प्रोग्रामिंग भाषाओं की तुलना (स्ट्रिंग फ़ंक्शंस)|प्रोग्रामिंग लैंग्वेज की तुलना (रज्जु फलनो)]]
* लेवी की लेम्मा
* [[लेवी की लेम्मा]]
* स्ट्रिंग (कंप्यूटर विज्ञान)#औपचारिक सिद्धांत|स्ट्रिंग (कंप्यूटर विज्ञान) - स्ट्रिंग्स पर अधिक बुनियादी संचालन की परिभाषा और कार्यान्वयन
* [[रज्जु (कंप्यूटर विज्ञान)]] - रज्जु पर अधिक मूल संचालन की परिभाषा और कार्यान्वयन


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 190: Line 166:
* {{cite book | first1=John E. | last1=Hopcroft | first2=Jeffrey D. | last2=Ullman | title=Introduction to Automata Theory, Languages and Computation | publisher=Addison-Wesley Publishing | location=Reading, Massachusetts | year=1979 | isbn=978-0-201-02988-8 | zbl=0426.68001 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }} ''(See chapter 3.)''
* {{cite book | first1=John E. | last1=Hopcroft | first2=Jeffrey D. | last2=Ullman | title=Introduction to Automata Theory, Languages and Computation | publisher=Addison-Wesley Publishing | location=Reading, Massachusetts | year=1979 | isbn=978-0-201-02988-8 | zbl=0426.68001 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }} ''(See chapter 3.)''
{{reflist}}
{{reflist}}
[[Category: औपचारिक भाषाएँ]] [[Category: संबंधपरक बीजगणित]] [[Category: स्ट्रिंग (कंप्यूटर विज्ञान)|संचालन]]


[[Category: Machine Translated Page]]
[[Category:All articles with unsourced statements]]
[[Category:Articles with unsourced statements from August 2017]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:औपचारिक भाषाएँ]]
[[Category:संबंधपरक बीजगणित]]
[[Category:स्ट्रिंग (कंप्यूटर विज्ञान)|संचालन]]

Latest revision as of 16:20, 17 October 2023

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

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

एक रज्जु वर्णों का एक सीमित अनुक्रम है। रिक्त रज्जु को के द्वारा निरूपित किया जाता है। दो रज्जु और के संश्रृंखलन को या द्वारा दर्शाया जाता है। रिक्त रज्जु के साथ संश्रृंखलन करने से कोई अंतर नहीं पड़ता, । रज्जु का संश्रृंखलन साहचर्य है,

उदाहरण के लिए,

एक भाषा रज्जु का एक सीमित या अनंत समुच्चय है। सम्मिलन, सर्वनिष्ठ आदि जैसे सामान्य समुच्चय संक्रिया के अलावा, संश्रृंखलन को भाषाओं पर लागू किया जा सकता है, यदि और दोनों भाषाएँ हैं, तो वहाँ औपचारिक रूप से के लिय संश्रृंखलन को से किसी भी रज्जु और से किसी भी रज्जु के संश्रृंखलन के समुच्चय के रूप में परिभाषित किया गया है । फिर, संश्रृंखलन बिंदु को प्रायः संक्षिप्तता के लिए विलोपित कर दिया जाता है।

केवल रिक्त रज्जु वाली भाषा को रिक्त भाषा से प्रतिष्ठित करना है किसी भी भाषा को पहली भाषा के साथ श्रृंखलाबद्ध करने से कोई परिवर्तन नहीं होता है,, बाद वाले के साथ संश्रृंखलन करने पर हमेशा रिक्त भाषा उत्पन्न होती है, । भाषाओं का संश्रृंखलन साहचर्य है,

उदाहरण के लिए, को संक्षिप्त करने पर सभी तीन अंकों की दशमलव संख्याओं का समुच्चय के रूप में प्राप्त होता है। यादृच्छिक लंबाई की सभी दशमलव संख्याओं का समुच्चय एक अनंत भाषा के लिए एक उदाहरण है।

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

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

द्वारा दर्शायी जाती है। किसी भाषा की वर्णमाला उन सभी वर्णों का समुच्चय है जो औपचारिक रूप से ,, के किसी भी रज्जु में होते हैं।

उदाहरण के लिए, समुच्चय रज्जु की वर्णमाला है, और उपरोक्त उपरोक्त भाषा के साथ-साथ सभी दशमलव संख्याओं की भाषा की वर्णमाला है।

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

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

f(ε)=ε

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

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

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

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

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

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

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

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

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

  • fuc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹एसटीआरएएसएसई› } ∪ { ‹U› } ∪ { } = { ‹एसटीआरएएसएसई›, ‹U› }।

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

एक रज्जु समरूपता (प्रायः औपचारिक भाषा सिद्धांत में इसे केवल समरूपता के रूप में संदर्भित किया जाता है) एक रज्जु प्रतिस्थापन है जैसे कि प्रत्येक वर्ण को एक रज्जु द्वारा प्रतिस्थापित किया जाता है। अर्थात्, , जहां प्रत्येक वर्ण के लिए एक रज्जु है।[note 2][4]

रज्जु समरूपता मुक्त एकाभ पर मुफ़्त एकाभआकारिकी हैं, जो रिक्त रज्जु और रज्जु संश्रृंखलन के द्विआधारी संक्रिया को संरक्षित करते हैं। किसी भाषा को देखते हुए, समुच्चय को का समरूपी प्रतिबिम्ब कहा जाता है। एक रज्जु का व्युत्क्रम समरूपी प्रतिबिम्ब को

के रूप में परिभाषित किया गया है, जबकि किसी भाषा के व्युत्क्रम समरूपी प्रतिबिम्ब को

के रूप में परिभाषित किया जाता है, सामान्य तौर पर, , जबकि किसी भाषा के लिए

और

होते हैं।

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

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

उपरोक्त प्रतिस्थापन के समान परिभाषित करके एक उदाहरण रज्जु समरूपता gucभी प्राप्त किया जा सकता है, guc(‹a›) = ‹A›, ..., guc(‹0›) = ε, लेकिन लेकिन विराम चिन्हों पर guc को अपरिभाषित रहने देना। व्युत्क्रम समरूपी प्रतिबिम्बो के उदाहरण हैं

  • guc−1({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, क्योंकि guc(‹sss›) = guc(‹sß›) = guc(‹ßs›) = ‹SSS›, और
  • guc−1({ ‹A›, ‹bb› }) = { ‹a› }, क्योंकि guc(‹a›) = ‹A›, जबकि ‹bb› तक guc द्वारा नहीं पहुंचा जा सकता।

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

एक बहुत ही सरल रज्जु समरूपता उदाहरण जो प्रत्येक वर्ण को केवल एक वर्ण में मानचित्रित करता है तथा वह इबीसीडीआईसी-कूटबद्‍ध रज्जु को एएससीआईआई में परिवर्तित करता है।

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

यदि s एक रज्जु है, और एक वर्णमाला है, तो s का रज्जु प्रक्षेपण वह रज्जु है जिसके परिणामस्वरूप उन सभी वर्णों को हटा दिया जाता है जो में नहीं हैं।`इसे के रूप में लिखा जाता है। इसे औपचारिक रूप से दाहिनी ओर से वर्णों को हटाकर परिभाषित किया गया है,

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

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

द्वारा दिया जाता है।

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

रज्जु s से किसी वर्ण a का दायां भागफल, रज्जु s में वर्ण a का दाहिनी ओर से छिन्न है। इसे के रूप में दर्शाया गया है। यदि रज्जु में दाहिनी ओर a नहीं है, तो परिणाम रिक्त रज्जु होगा। इस प्रकार,

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

इसी प्रकार, एक एकाभ का उपसमुच्चय दिए जाने पर, भागफल उपसमुच्चय को

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

हॉपक्रॉफ्ट और उल्मैन (1979) भाषाओं L1 और L2 के भागफल L1/L2 को एलL1 को L1/L2 = { s | ∃tL2. stL1 } के समान वर्णमाला पर परिभाषित करते हैं।[7] यह उपरोक्त परिभाषा का सामान्यीकरण नहीं है, क्योंकि, एक रज्जु s और अलग-अलग वर्णों a, b के लिए, हॉपक्रॉफ्ट और उलमैन की परिभाषा का तात्पर्य { ε } के बजाय अनुवर्ती {} है।

एक एकल भाषा L1 और एक यादृच्छिक भाषा L2 के बाएँ भागफल (जब हॉपक्रॉफ्ट और उलमैन 1979 के समान परिभाषित किया गया) को ब्रज़ोज़ोस्की अवकलज के रूप में जाना जाता है, यदि L2 कोनियमित अभिव्यक्ति द्वारा दर्शाया जाता है, तो बायां भागफल भी हो सकता है।[8]

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

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

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

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

दक्षिण निरस्तीकरण

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

के रूप में परिभाषित किया गया है, रिक्त रज्जु हमेशा रद्द करने योग्य होती है,

स्पष्ट रूप से, दक्षिण निरस्तीकरण और प्रक्षेपण क्रमविनिमेय आवागमन.

उपसर्ग

एक रज्जु के उपसर्ग किसी दी गई भाषा के संबंध में, एक रज्जु के सभी उपसर्गों का समुच्चय है,

जहाँ है ।

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

है।

उदाहरण,
किसी भाषा को उपसर्ग संवृत कहा जाता है यदि हो।

उपसर्ग संवृत करने वाला संचालक निष्क्रिय है,

उपसर्ग संबंध एक द्विआधारी संबंध है उपसर्ग संबंध एक द्विआधारी संबंध है यदि है। यह संबंध उपसर्ग क्रम का एक विशेष उदाहरण है।

यह भी देखें

टिप्पणियाँ

  1. Although every regular language is also context-free, the previous theorem is not implied by the current one, since the former yields a shaper result for regular languages.
  2. Strictly formally, a homomorphism yields a language consisting of just one string, i.e. .
  3. This follows from the above-mentioned closure under arbitrary substitutions.


संदर्भ

  • 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.)
  1. Hopcroft, Ullman (1979), Sect.3.2, p.60
  2. Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60
  3. Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131
  4. Hopcroft, Ullman (1979), Sect.3.2, p.60-61
  5. Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61
  6. Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132
  7. Hopcroft, Ullman (1979), Sect.3.2, p.62
  8. Janusz A. Brzozowski (1964). "रेगुलर एक्सप्रेशन के व्युत्पन्न". J ACM. 11 (4): 481–494. doi:10.1145/321239.321249. S2CID 14126942.