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

From Vigyanwiki
No edit summary
 
(13 intermediate revisions by 4 users not shown)
Line 73: Line 73:
<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>
नियमित भाषाओं का वर्ग समरूपता और व्युत्क्रम समरूपता के अंतर्गत संवृत है।<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>f(a) \neq \varepsilon</math> वर्णमाला में सभी के लिए <math>\Sigma</math>. सरल एकल-अक्षर [[प्रतिस्थापन सिफर]] (ε-मुक्त) रज्जु समरूपता के उदाहरण हैं।


एक उदाहरण रज्जु समरूपता जी<sub>uc</sub> #स्ट्रिंग_प्रतिस्थापन प्रतिस्थापन के समान परिभाषित करके भी प्राप्त किया जा सकता है: जी<sub>uc</sub>(‹ए›) = ‹ए›, ..., जी<sub>uc</sub>(‹0›) = ε, लेकिन g देना<sub>uc</sub> विराम चिन्हों पर अपरिभाषित रहें।
एक रज्जु समरूपता को ε-मुक्त (या e-मुक्त) कहा जाता है यदि वर्णमाला <math>\Sigma</math> में सभी a के लिए <math>f(a) \neq \varepsilon</math> हो। सरल एकल-अक्षर [[प्रतिस्थापन सिफर|प्रतिस्थापन संकेताक्षर]] (ε-मुक्त) रज्जु समरूपता के उदाहरण हैं।
<!---omitted, since sloppy notation, anyway, see above---
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.
--->
व्युत्क्रम समरूपी प्रतिबिम्बयों के उदाहरण हैं
* जी<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]] में परिवर्तित करना है।
उपरोक्त प्रतिस्थापन के समान परिभाषित करके एक उदाहरण रज्जु समरूपता g<sub>uc</sub>भी प्राप्त किया जा सकता है, g<sub>uc</sub>(‹a›) = ‹A›, ..., g<sub>uc</sub>(‹0›) = ε, लेकिन लेकिन विराम चिन्हों पर g<sub>uc</sub> को अपरिभाषित रहने देना। व्युत्क्रम समरूपी प्रतिबिम्बो के उदाहरण हैं
* 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›, और
*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› से ε तक मानचित्रित करता है।
 
एक बहुत ही सरल रज्जु समरूपता उदाहरण जो प्रत्येक वर्ण को केवल एक वर्ण में मानचित्रित करता है तथा वह [[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 96: 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 137: 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 175: 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.