डाइक लैंग्वेज: Difference between revisions

Latest revision as of 10:15, 22 August 2023

लंबाई 8 के 14 डाइक शब्दों की लैटिस - [ और ] की व्याख्या ऊपर और नीचे के रूप में की गई है।

कंप्यूटर विज्ञान, गणित और लैंग्वेज विज्ञान की औपचारिक लैंग्वेजेज के सिद्धांत में, डाइक शब्द कोष्ठक की संतुलित स्ट्रिंग है।

डाइक शब्दों का समूह डाइक लैंग्वेज का निर्माण करता है। सबसे सरल, D1, केवल दो युग्मित होने वाले कोष्ठकों का उपयोग करता है।

डाइक शब्द और लैंग्वेज का नाम गणितज्ञ वाल्थर वॉन डाइक के नाम पर रखा गया है। उनके पास अभिव्यक्तियों के विश्लेषण में अनुप्रयोग होते हैं जिनमें कोष्ठक का उचित प्रकार से नेस्टेड अनुक्रम होना चाहिए, जैसे अंकगणित या बीजगणितीय अभिव्यक्तियाँ होती है।

औपचारिक परिभाषा

मान लीजिये कि $\Sigma =\{[,]\}$ [और] प्रतीकों से युक्त वर्णमाला बनती है। मान लीजिये कि $\Sigma ^{*}$ इसके क्लेन क्लोजर को दर्शाता है। डाइक लैंग्वेज को इस प्रकार परिभाषित किया गया है:

\{u\in \Sigma ^{*}\vert {\text{ all prefixes of }}u{\text{ contain no more ]'s than ['s}}{\text{ and the number of ['s in }}u{\text{ equals the number of ]'s}}\}.

संदर्भ-मुक्त व्याकरण

कुछ स्थितियों में संदर्भ-मुक्त व्याकरण के माध्यम से डाइक लैंग्वेज को परिभाषित करना सहायक हो सकता है। डाइक लैंग्वेज एकल गैर-टर्मिनल $S$ के साथ संदर्भ-मुक्त व्याकरण द्वारा उत्पन्न होती है, और उत्पादन:

S \to ε | "[" S "]" S

अर्थात्, S या तो रिक्त स्ट्रिंग है ( $ε$ ) या [डाइक लैंग्वेज का तत्व, मिलान], और डाइक लैंग्वेज का तत्व है।

डाइक लैंग्वेज के लिए वैकल्पिक संदर्भ-मुक्त व्याकरण उत्पादन द्वारा दिया गया है:

S \to ("[" S "]") *

अर्थात्, S, [डाइक लैंग्वेज का तत्व, और मिलान] के संयोजन की शून्य या अधिक घटना है, जहां उत्पादन के दाईं ओर डाइक लैंग्वेज के कई तत्व एक-दूसरे से भिन्न होने के लिए स्वतंत्र हैं।

वैकल्पिक परिभाषा

इसके अतिरिक्त अन्य संदर्भों में डाइक लैंग्वेज को विभाजित करके परिभाषित करना सहायक हो सकता है $\Sigma ^{*}$ को समतुल्य वर्गों में, निम्नानुसार विभाजित किया जाता है। किसी भी तत्व के लिए $u\in \Sigma ^{*}$ लम्बाई का $|u|$ , हम आंशिक कार्यों को परिभाषित करते हैं $\operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}$ और $\operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}$ द्वारा;

\operatorname {insert} (u,j)

है

u

साथ

[]

में डाला गया

j

वां स्थान है।

\operatorname {delete} (u,j)

है

u

साथ

[]

से विस्थापित किया गया

j

वां स्थान है।

इस समझ के साथ $\operatorname {insert} (u,j)$ के लिए अपरिभाषित है $j>|u|$ और $\operatorname {delete} (u,j)$ अपरिभाषित है यदि $j>|u|-2$ है। हम तुल्यता संबंध को परिभाषित करते हैं $R$ पर $\Sigma ^{*}$ इस प्रकार है: तत्वों के लिए $a,b\in \Sigma ^{*}$ अपने पास $(a,b)\in R$ यदि और केवल शून्य या अधिक अनुप्रयोगों का अनुक्रम उपस्थित है $\operatorname {insert}$ और $\operatorname {delete}$ से प्रारम्भ होने वाले फलन $a$ और $b$ के साथ समाप्त हो रहा है। शून्य संक्रियाओं के अनुक्रम की अनुमति रिफ्लेक्सिविटी $R$ के कारण होती है। सममित संबंध तार्किक परिणाम का अवलोकन है कि अनुप्रयोगों का कोई भी परिमित अनुक्रम $\operatorname {insert}$ स्ट्रिंग को अनुप्रयोगों के सीमित अनुक्रम के साथ पूर्ववत $\operatorname {delete}$ किया जा सकता है। परिभाषा से सकर्मक संबंध स्पष्ट है।

तुल्यता संबंध $\Sigma ^{*}$ समतुल्य वर्गों में लैंग्वेज को विभाजित करता है। यदि हम लेते हैं $\epsilon$ रिक्त स्ट्रिंग को दर्शाने के लिए, तब समतुल्य वर्ग के अनुरूप लैंग्वेज $\operatorname {Cl} (\epsilon )$ डाइक लैंग्वेज कहलाती है।

गुण

डाइक लैंग्वेज को संघनन की क्रिया के अंतर्गत विवृत किया जाता है।
प्रक्रिया करके $\Sigma ^{*}$ संयोजन के अंतर्गत बीजगणितीय मोनॉइड के रूप में हम देखते हैं कि मोनॉइड संरचना भागफल मोनॉइड $\Sigma ^{*}/R$ पर स्थानांतरित होती है, जिसके परिणामस्वरूप डाइक लैंग्वेज का वाक्य-विन्यास मोनॉइड बनता है। वर्ग $\operatorname {Cl} (\epsilon )$ को $1$ के रूप में निरूपित किया जाता है।
डाइक लैंग्वेज का वाक्यविन्यास मोनॉइड क्रमविनिमेय नहीं है: यदि $u=\operatorname {Cl} ([)$ और $v=\operatorname {Cl} (])$ तब $uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu$ है।
उपरोक्त संकेतन के साथ, $uv=1$ किन्तु दोनों में से कोई नहीं $u$ और न $v$ में $\Sigma ^{*}/R$ व्युत्क्रमणीय हैं।
डाइक लैंग्वेज का वाक्य-विन्यास मोनॉइड, गुणों के आधार पर बाइसिकल सेमीग्रुप के लिए आइसोमोर्फिक है $\operatorname {Cl} ([)$ और $\operatorname {Cl} (])$ ऊपर वर्णित है।
चॉम्स्की-शूट्ज़ेनबर्गर प्रतिनिधित्व प्रमेय के अनुसार, कोई भी संदर्भ-मुक्त लैंग्वेज एक या अधिक प्रकार के ब्रैकेट युग्म पर डाइक लैंग्वेज के साथ कुछ नियमित लैंग्वेज के प्रतिच्छेदन की समरूप छवि है।^[1]
दो भिन्न-भिन्न प्रकार के ब्रैकेट वाली डाइक लैंग्वेज को समष्टिता वर्ग $TC^{0}$ में पहचाना जा सकता है।^[2]
$n$ कोष्ठकों के युग्म और $k$ अंतरतम युग्म (अर्थात् सबस्ट्रिंग $[\ ]$ ) के साथ भिन्न-भिन्न डाइक शब्दों की संख्या नारायण संख्या $\operatorname {N} (n,k)$ है।
$n$ कोष्ठकों के युग्म के साथ भिन्न-भिन्न डाइक शब्दों की संख्या $n$ -वीं कैटलन संख्या $C_{n}$ है। ध्यान दें कि $n$ कोष्ठक युग्म वाले शब्दों की डाइक लैंग्वेज $k$ अंतरतम युग्म वाले $n$ कोष्ठक युग्म वाले शब्दों की डाइक लैंग्वेज के सभी संभावित $k$ के संघ के समान है, जैसा कि पिछले बिंदु में परिभाषित किया गया है। चूँकि $k$ 0 से $n$ तक हो सकता है , हमें निम्नलिखित समानता प्राप्त होती है, जो वास्तव में मान्य है:

C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)

उदाहरण

हम तुल्यता संबंध को परिभाषित कर सकते हैं डाइक लैंग्वेज $L$ पर ${\mathcal {D}}$ है। $u,v\in {\mathcal {D}}$ के लिए अपने पास $(u,v)\in L$ यदि और केवल $|u|=|v|$ है, अर्थात $u$ और $v$ की लंबाई समान है। यह संबंध डाइक लैंग्वेज को विभाजित करता है: ${\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}$ अपने पास ${\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}$ है। जहाँ ${\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}$ है। ध्यान दें कि ${\mathcal {D}}_{n}$ विषम $n$ के लिए रिक्त है।

लंबाई के डाइक शब्दों का परिचय देते हुए $n$ , हम उन पर संबंध प्रस्तुत कर सकते हैं। प्रत्येक $n\in \mathbb {N}$ के लिए हम संबंध $S_{n}$ पर ${\mathcal {D}}_{n}$ को परिभाषित करते हैं; $u,v\in {\mathcal {D}}_{n}$ के लिए अपने पास $(u,v)\in S_{n}$ यदि और केवल $v$ से $u$ उचित स्वैप की श्रृंखला द्वारा पहुंचा जा सकता है। शब्द में उचित स्वैप $u\in {\mathcal {D}}_{n}$ '][' की घटना को '[]' से परिवर्तित कर देता है। प्रत्येक $n\in \mathbb {N}$ के लिए संबंध $S_{n}$ बनाता है ${\mathcal {D}}_{n}$ आंशिक रूप से क्रमित किए गए समुच्चय में है। संबंध $S_{n}$ प्रतिवर्ती संबंध है क्योंकि उचित स्वैप का रिक्त अनुक्रम $u$ को $u$ होता है। सकर्मक संबंध इस प्रकार है क्योंकि हम उचित स्वैप के अनुक्रम $u$ को $v$ का विस्तार कर सकते हैं इसे उचित स्वैप के अनुक्रम के साथ जोड़कर $v$ को $w$ अनुक्रम बनाना जो $u$ में $w$ लेता है। उसे देखने के लिए $S_{n}$ भी एंटीसिमेट्रिक संबंध है, हम सहायक फलन $\sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N}$ का परिचय देते हैं सभी उपसर्गों के योग के रूप में $v$ का $u$ परिभाषित किया गया है:

:

\sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}

निम्न तालिका इसे दर्शाती है $\sigma _{n}$ उचित स्वैप के संबंध में मोनोटोनिक फलन है।

$\sigma _{n}$ का स्ट्रिक्ट मोनोटोनिसिटी
$\sigma _{n}(u)$ का आंशिक योग	$P$	$P-1$	$P$	$Q$
$u$	$\ldots$	]	[	$\ldots$
$u'$	$\ldots$	[	]	$\ldots$
$\sigma _{n}(u')$ का आंशिक योग	$P$	$P+1$	$P$	$Q$
आंशिक योग का अंतर	0	2	0	0

इस प्रकार $\sigma _{n}(u')-\sigma _{n}(u)=2>0$ इसलिए $\sigma _{n}(u)<\sigma _{n}(u')$ जब कोई उचित परिवर्तन होता है तो वह $u$ में $u'$ होता है। अब यदि हम मान लें कि दोनों $(u,v),(v,u)\in S_{n}$ और $u\neq v$ , तो उचित स्वैप के गैर-रिक्त अनुक्रम होते हैं $u$ में $v$ लिया जाता है और इसके विपरीत है। परन्तु फिर $\sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)$ जो कि निरर्थक है। अत: जब भी दोनों $(u,v)$ और $(v,u)$ में हैं $S_{n}$ , हमारे पास $u=v$ है, इस प्रकार $S_{n}$ एंटीसिमेट्रिक है।

आंशिक आदेशित समुच्चय $D_{8}$ यदि हम [ऊपर जाने के रूप में और] नीचे जाने के रूप में व्याख्या करते हैं तो इसे परिचय के साथ दिए गए चित्रण में दिखाया गया है।

सामान्यीकरण

कई सीमांककों के साथ डाइक लैंग्वेज के भिन्न रूप उपस्थित हैं, उदाहरण के लिए, वर्णमाला "(", ")", "[", और "]" पर D2 है। ऐसी लैंग्वेज के शब्द वे होते हैं जो सभी सीमांककों के लिए उचित प्रकार से कोष्ठक में होते हैं, अर्थात, कोई शब्द को बाएं से दाएं पढ़ सकता है, स्टैक पर प्रत्येक ओपनिंग डिलीमीटर को पुश कर सकता है, और जब भी हम क्लोजिंग डिलीमीटर पर पहुंचते हैं तो हमें स्टैक के शीर्ष से युग्मित होने वाले ओपनिंग डिलीमीटर को पॉप करने में सक्षम होना चाहिए। (उपरोक्त गणना एल्गोरिथ्म सामान्यीकरण नहीं करता है)।

यह भी देखें

डाइक सर्वांगसमता
लैटिस शब्द

संदर्भ

[1] Kambites, Communications in Algebra Volume 37 Issue 1 (2009) 193-208

[2] Barrington and Corbett, Information Processing Letters 32 (1989) 251-256

[1]

[2]

@@ Line 1: / Line 1: @@
 {{short description|Language consisting of balanced strings of brackets}}
-[[File:Dyck lattice D4.svg|thumb|लंबाई 8 के 14 डाइक शब्दों की जाली - [ और ] की व्याख्या ऊपर और नीचे के रूप में की गई है]][[कंप्यूटर विज्ञान]], गणित और [[भाषा विज्ञान|लैंग्वेज विज्ञान]] की औपचारिक भाषाओं के सिद्धांत में,  डाइक शब्द  संतुलित स्ट्रिंग (कंप्यूटर विज्ञान)#कोष्ठक का औपचारिक सिद्धांत है।
+[[File:Dyck lattice D4.svg|thumb|लंबाई 8 के 14 डाइक शब्दों की लैटिस - [ और ] की व्याख्या ऊपर और नीचे के रूप में की गई है।]][[कंप्यूटर विज्ञान]], गणित और [[भाषा विज्ञान|लैंग्वेज विज्ञान]] की औपचारिक लैंग्वेजेज के सिद्धांत में, '''डाइक शब्द''' कोष्ठक की संतुलित स्ट्रिंग है।
-डाइक शब्दों का समूह डाइक लैंग्वेज बनाता है। सबसे सरल, D1, केवल दो मेल खाने वाले कोष्ठकों का उपयोग करता है, उदा. ( और )।
+डाइक शब्दों का समूह '''डाइक लैंग्वेज''' का निर्माण करता है। सबसे सरल, D1, केवल दो युग्मित होने वाले कोष्ठकों का उपयोग करता है।
-डाइक शब्द और लैंग्वेज का नाम गणितज्ञ [[वाल्थर वॉन डाइक]] के नाम पर रखा गया है। उनके पास अभिव्यक्तियों के विश्लेषण में अनुप्रयोग होते हैं जिनमें कोष्ठक का सही ढंग से नेस्टेड अनुक्रम होना चाहिए, जैसे अंकगणित या बीजगणितीय अभिव्यक्तियाँ।
+डाइक शब्द और लैंग्वेज का नाम गणितज्ञ [[वाल्थर वॉन डाइक]] के नाम पर रखा गया है। उनके पास अभिव्यक्तियों के विश्लेषण में अनुप्रयोग होते हैं जिनमें कोष्ठक का उचित प्रकार से नेस्टेड अनुक्रम होना चाहिए, जैसे अंकगणित या बीजगणितीय अभिव्यक्तियाँ होती है।
 ==औपचारिक परिभाषा==
-होने देना <math>\Sigma = \{ [, ] \}</math> [ और ] प्रतीकों से युक्त वर्णमाला बनें। होने देना <math>\Sigma^{*}</math> इसके [[क्लीन क्लोजर]] को निरूपित करें।
+मान लीजिये कि <math>\Sigma = \{ [, ] \}</math> [और] प्रतीकों से युक्त वर्णमाला बनती है। मान लीजिये कि <math>\Sigma^{*}</math> इसके [[क्लीन क्लोजर|क्लेन क्लोजर]] को दर्शाता है। डाइक लैंग्वेज को इस प्रकार परिभाषित किया गया है:
-डाइक लैंग्वेज को इस प्रकार परिभाषित किया गया है:
 : <math>\{ u \in \Sigma^* \vert \text{ all prefixes of } u \text{ contain no more ]'s than ['s} \text{ and the number of ['s in } u \text{ equals the number of ]'s}\}.</math>
 [[संदर्भ-मुक्त व्याकरण|'''संदर्भ-मुक्त व्याकरण''']]
-कुछ स्थितियों में संदर्भ-मुक्त व्याकरण के माध्यम से डाइक लैंग्वेज को परिभाषित करना सहायक हो सकता है।
+कुछ स्थितियों में संदर्भ-मुक्त व्याकरण के माध्यम से डाइक लैंग्वेज को परिभाषित करना सहायक हो सकता है। डाइक लैंग्वेज एकल गैर-टर्मिनल {{math|''S''}} के साथ संदर्भ-मुक्त व्याकरण द्वारा उत्पन्न होती है, और उत्पादन:
-डाइक लैंग्वेज ल गैर-टर्मिनल के साथ संदर्भ-मुक्त व्याकरण द्वारा उत्पन्न होती है {{math|''S''}}, और उत्पादन:
 : {{math|''S'' → ''ε'' {{pipe}} "[" ''S'' "]" ''S''}}
-अर्थात्, S या तो [[खाली स्ट्रिंग]] है ({{math|''ε''}}) या है [ , डाइक लैंग्वेज का  तत्व, मिलान ] , और डाइक लैंग्वेज का  तत्व।
+अर्थात्, S या तो [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] है ({{math|''ε''}}) या [डाइक लैंग्वेज का तत्व, मिलान], और डाइक लैंग्वेज का तत्व है।
-डाइक लैंग्वेज के लिए  वैकल्पिक संदर्भ-मुक्त व्याकरण उत्पादन द्वारा दिया गया है:
+डाइक लैंग्वेज के लिए वैकल्पिक संदर्भ-मुक्त व्याकरण उत्पादन द्वारा दिया गया है:
 : {{math|''S'' → ("[" ''S'' "]")<sup>*</sup>}}
-अर्थात्, एस, डाइक लैंग्वेज का  तत्व, और  मिलान] के संयोजन का [[ क्लेन स्टार ]] है, जहां उत्पादन के दाईं ओर डाइक लैंग्वेज के कई तत्व  दूसरे से भिन्न होने के लिए स्वतंत्र हैं।
+अर्थात्, S, [डाइक लैंग्वेज का तत्व, और मिलान] के संयोजन की [[ क्लेन स्टार |शून्य या अधिक घटना]] है, जहां उत्पादन के दाईं ओर डाइक लैंग्वेज के कई तत्व एक-दूसरे से भिन्न होने के लिए स्वतंत्र हैं।
 === वैकल्पिक परिभाषा ===
-इसके अतिरिक्त अन्य संदर्भों में डाइक लैंग्वेज को विभाजित करके परिभाषित करना सहायक हो सकता है <math>\Sigma^{*}</math> समतुल्य वर्गों में, निम्नानुसार।
+इसके अतिरिक्त अन्य संदर्भों में डाइक लैंग्वेज को विभाजित करके परिभाषित करना सहायक हो सकता है <math>\Sigma^{*}</math> को समतुल्य वर्गों में, निम्नानुसार विभाजित किया जाता है। किसी भी तत्व के लिए <math>u \in \Sigma^{*}</math> लम्बाई का <math>| u |</math>, हम [[आंशिक कार्य|आंशिक कार्यों]] को परिभाषित करते हैं <math>\operatorname{insert} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*}</math> और <math>\operatorname{delete} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*}</math> द्वारा;
-किसी भी तत्व के लिए <math>u \in \Sigma^{*}</math> लम्बाई का <math>| u |</math>, हम [[आंशिक कार्य]]ों को परिभाषित करते हैं <math>\operatorname{insert} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*}</math> और <math>\operatorname{delete} : \Sigma^{*} \times \mathbb{N} \rightarrow \Sigma^{*}</math> द्वारा
-:<math>\operatorname{insert}(u, j)</math> है <math>u</math> साथ<math>[]</math>में डाला गया <math>j</math>वां स्थान
+:<math>\operatorname{insert}(u, j)</math> है <math>u</math> साथ<math>[]</math>में डाला गया <math>j</math>वां स्थान है।
-:<math>\operatorname{delete}(u, j)</math> है <math>u</math> साथ<math>[]</math>से हटा दिया गया <math>j</math>वां स्थान
+:<math>\operatorname{delete}(u, j)</math> है <math>u</math> साथ<math>[]</math>से विस्थापित किया गया <math>j</math>वां स्थान है।
-इस समझ के साथ <math>\operatorname{insert}(u, j)</math> के लिए अपरिभाषित है <math>j > |u|</math> और <math>\operatorname{delete}(u, j)</math> अपरिभाषित है यदि <math>j > |u| - 2</math>. हम  तुल्यता संबंध को परिभाषित करते हैं <math>R</math> पर <math>\Sigma^{*}</math> इस प्रकार: तत्वों के लिए <math>a, b \in \Sigma^{*}</math> अपने पास <math>(a, b) \in R</math> यदि और केवल यदि शून्य या अधिक अनुप्रयोगों का अनुक्रम मौजूद है <math>\operatorname{insert}</math> और <math>\operatorname{delete}</math> से शुरू होने वाले कार्य <math>a</math> और के साथ समाप्त हो रहा है <math>b</math>. शून्य संक्रियाओं के अनुक्रम को [[प्रतिवर्ती संबंध]] के लिए अनुमति दी गई है <math>R</math>. [[सममित संबंध]] [[तार्किक परिणाम]] का अवलोकन है कि अनुप्रयोगों का कोई भी परिमित अनुक्रम <math>\operatorname{insert}</math>  स्ट्रिंग को अनुप्रयोगों के  सीमित अनुक्रम के साथ पूर्ववत किया जा सकता है <math>\operatorname{delete}</math>. [[सकर्मक संबंध]] परिलैंग्वेज से स्पष्ट है।
+इस समझ के साथ <math>\operatorname{insert}(u, j)</math> के लिए अपरिभाषित है <math>j > |u|</math> और <math>\operatorname{delete}(u, j)</math> अपरिभाषित है यदि <math>j > |u| - 2</math> है। हम तुल्यता संबंध को परिभाषित करते हैं <math>R</math> पर <math>\Sigma^{*}</math> इस प्रकार है: तत्वों के लिए <math>a, b \in \Sigma^{*}</math> अपने पास <math>(a, b) \in R</math> यदि और केवल शून्य या अधिक अनुप्रयोगों का अनुक्रम उपस्थित है <math>\operatorname{insert}</math> और <math>\operatorname{delete}</math> से प्रारम्भ होने वाले फलन <math>a</math> और <math>b</math> के साथ समाप्त हो रहा है। शून्य संक्रियाओं के अनुक्रम की अनुमति [[प्रतिवर्ती संबंध|रिफ्लेक्सिविटी]] <math>R</math> के कारण होती है। [[सममित संबंध]] [[तार्किक परिणाम]] का अवलोकन है कि अनुप्रयोगों का कोई भी परिमित अनुक्रम <math>\operatorname{insert}</math>  स्ट्रिंग को अनुप्रयोगों के सीमित अनुक्रम के साथ पूर्ववत <math>\operatorname{delete}</math> किया जा सकता है। परिभाषा से [[सकर्मक संबंध]] स्पष्ट है।
-तुल्यता संबंध लैंग्वेज को विभाजित करता है <math>\Sigma^{*}</math> समतुल्य वर्गों में। अगर हम लेते हैं <math>\epsilon</math> खाली स्ट्रिंग को दर्शाने के लिए, फिर समतुल्य वर्ग के अनुरूप लैंग्वेज <math>\operatorname{Cl}(\epsilon)</math> डाइक लैंग्वेज कहलाती है।
+तुल्यता संबंध <math>\Sigma^{*}</math> समतुल्य वर्गों में लैंग्वेज को विभाजित करता है। यदि हम लेते हैं <math>\epsilon</math> रिक्त स्ट्रिंग को दर्शाने के लिए, तब समतुल्य वर्ग के अनुरूप लैंग्वेज <math>\operatorname{Cl}(\epsilon)</math> डाइक लैंग्वेज कहलाती है।
 ==गुण==
-* डाइक लैंग्वेज को संघनन की क्रिया के अंतर्गत बंद किया जाता है।
+* डाइक लैंग्वेज को संघनन की क्रिया के अंतर्गत विवृत किया जाता है।
-*इलाज करके <math>\Sigma^{*}</math> संयोजन के तहत  बीजगणितीय [[मोनोइड]] के रूप में हम देखते हैं कि मोनॉइड संरचना भागफल मोनॉइड पर स्थानांतरित होती है <math>\Sigma^{*} / R</math>, जिसके परिणामस्वरूप डाइक लैंग्वेज का वाक्य-विन्यास मोनोइड बनता है। कक्षा <math>\operatorname{Cl}(\epsilon)</math> निरूपित किया जाएगा <math>1</math>.
+*प्रक्रिया करके <math>\Sigma^{*}</math> संयोजन के अंतर्गत बीजगणितीय [[मोनोइड|मोनॉइड]] के रूप में हम देखते हैं कि मोनॉइड संरचना भागफल मोनॉइड <math>\Sigma^{*} / R</math> पर स्थानांतरित होती है, जिसके परिणामस्वरूप '''डाइक लैंग्वेज''' का वाक्य-विन्यास मोनॉइड बनता है। वर्ग  <math>\operatorname{Cl}(\epsilon)</math> को <math>1</math> के रूप में निरूपित किया जाता है।
-* डाइक लैंग्वेज का वाक्यविन्यास मोनोइड क्रम[[विनिमेय]] नहीं है: यदि <math>u = \operatorname{Cl}([)</math> और <math>v = \operatorname{Cl}(])</math> तब <math>uv = \operatorname{Cl}([]) = 1 \ne \operatorname{Cl}(][) = vu</math>.
+* डाइक लैंग्वेज का वाक्यविन्यास मोनॉइड [[विनिमेय|क्रमविनिमेय]] नहीं है: यदि <math>u = \operatorname{Cl}([)</math> और <math>v = \operatorname{Cl}(])</math> तब <math>uv = \operatorname{Cl}([]) = 1 \ne \operatorname{Cl}(][) = vu</math> है।
-* उपरोक्त संकेतन के साथ, <math>uv = 1</math> लेकिन नहीं <math>u</math> और न <math>v</math> में उलटे हैं <math>\Sigma^{*} / R</math>.
+* उपरोक्त संकेतन के साथ, <math>uv = 1</math> किन्तु दोनों में से कोई नहीं <math>u</math> और न <math>v</math> में <math>\Sigma^{*} / R</math> व्युत्क्रमणीय हैं।
-* डाइक लैंग्वेज का वाक्य-विन्यास मोनोइड, गुणों के आधार पर [[बाइसिकल अर्धसमूह]] के लिए आइसोमोर्फिक है <math>\operatorname{Cl}([)</math> और <math>\operatorname{Cl}(])</math> ऊपर वर्णित है।
+* डाइक लैंग्वेज का वाक्य-विन्यास मोनॉइड, गुणों के आधार पर [[बाइसिकल अर्धसमूह|बाइसिकल सेमीग्रुप]] के लिए आइसोमोर्फिक है <math>\operatorname{Cl}([)</math> और <math>\operatorname{Cl}(])</math> ऊपर वर्णित है।
-* चॉम्स्की-शूट्ज़ेनबर्गर प्रतिनिधित्व प्रमेय के अनुसार, कोई भी [[संदर्भ-मुक्त भाषा|संदर्भ-मुक्त]] लैंग्वेज  या अधिक प्रकार के ब्रैकेट जोड़े पर डाइक लैंग्वेज के साथ कुछ [[नियमित भाषा|नियमित]] लैंग्वेज के प्रतिच्छेदन की  समरूप छवि है।<ref>Kambites, Communications in Algebra Volume 37 Issue 1 (2009) 193-208</ref>
+* चॉम्स्की-शूट्ज़ेनबर्गर प्रतिनिधित्व प्रमेय के अनुसार, कोई भी [[संदर्भ-मुक्त भाषा|संदर्भ-मुक्त]] लैंग्वेज एक या अधिक प्रकार के ब्रैकेट युग्म पर डाइक लैंग्वेज के साथ कुछ [[नियमित भाषा|नियमित]] लैंग्वेज के प्रतिच्छेदन की समरूप छवि है।<ref>Kambites, Communications in Algebra Volume 37 Issue 1 (2009) 193-208</ref>
-* दो अलग-अलग प्रकार के ब्रैकेट वाली डाइक लैंग्वेज को [[जटिलता वर्ग]] TC0| में पहचाना जा सकता है<math>TC^{0}</math>.<ref>Barrington and Corbett, Information Processing Letters 32 (1989) 251-256</ref>
+* दो भिन्न-भिन्न प्रकार के ब्रैकेट वाली डाइक लैंग्वेज को [[जटिलता वर्ग|समष्टिता वर्ग]] <math>TC^{0}</math> में पहचाना जा सकता है।<ref>Barrington and Corbett, Information Processing Letters 32 (1989) 251-256</ref>
-* सटीक के साथ अलग-अलग डाइक शब्दों की संख्या {{mvar|n}} कोष्ठकों के जोड़े और {{mvar|k}} अंतरतम जोड़े (अर्थात् सबस्ट्रिंग <math>[\ ]</math>) [[नारायण संख्या]] है <math>\operatorname{N}(n, k)</math>.
+* {{mvar|n}} कोष्ठकों के युग्म और {{mvar|k}} अंतरतम युग्म (अर्थात् सबस्ट्रिंग <math>[\ ]</math>) के साथ भिन्न-भिन्न डाइक शब्दों की संख्या [[नारायण संख्या]] <math>\operatorname{N}(n, k)</math> है।
-* सटीक के साथ अलग-अलग डाइक शब्दों की संख्या {{mvar|n}} कोष्ठकों का युग्म है {{mvar|n}}-वाँ [[कैटलन संख्या]] <math>C_n</math>. ध्यान दें कि शब्दों की डाइक लैंग्वेज {{mvar|n}} कोष्ठक युग्म संघ के बराबर है, सब से अधिक संभव है {{mvar|k}}, डाइक भाषाओं के शब्दों का {{mvar|n}} कोष्ठक जोड़े के साथ {{mvar|k}} अंतरतम जोड़े, जैसा कि पिछले बिंदु में परिभाषित किया गया है। तब से {{mvar|k}} 0 से लेकर तक हो सकता है {{mvar|n}}, हमें निम्नलिखित समानता प्राप्त होती है, जो वास्तव में मान्य है:
+* {{mvar|n}} कोष्ठकों के युग्म के साथ भिन्न-भिन्न डाइक शब्दों की संख्या {{mvar|n}}-वीं [[कैटलन संख्या]] <math>C_n</math>है। ध्यान दें कि {{mvar|n}} कोष्ठक युग्म वाले शब्दों की डाइक लैंग्वेज {{mvar|k}} अंतरतम युग्म वाले {{mvar|n}} कोष्ठक युग्म वाले शब्दों की डाइक लैंग्वेज के सभी संभावित {{mvar|k}} के संघ के समान है, जैसा कि पिछले बिंदु में परिभाषित किया गया है। चूँकि {{mvar|k}} 0 से {{mvar|n}} तक हो सकता है , हमें निम्नलिखित समानता प्राप्त होती है, जो वास्तव में मान्य है:
 ::<math>C_n = \sum_{k=1}^n \operatorname{N}(n, k)</math>
 == उदाहरण ==
-हम  तुल्यता संबंध को परिभाषित कर सकते हैं <math>L</math> डाइक लैंग्वेज पर <math>\mathcal{D}</math>. के लिए <math>u,v\in\mathcal{D}</math> अपने पास <math>(u,v)\in L</math> अगर और केवल अगर <math>|u| = |v|</math>, अर्थात। <math>u</math> और <math>v</math> समान लंबाई हो. यह संबंध डाइक लैंग्वेज को विभाजित करता है: <math>\mathcal{D} / L = \{\mathcal{D}_0,\mathcal{D}_1,\ldots\}</math>. अपने पास <math>\mathcal{D} = \mathcal{D}_{0} \cup \mathcal{D}_{2} \cup \mathcal{D}_{4} \cup \ldots = \bigcup_{n=0}^{\infty} \mathcal{D}_{n}</math> कहाँ <math>\mathcal{D}_{n} = \{ u\in\mathcal{D} \mid |u| = n\}</math>. ध्यान दें कि <math>\mathcal{D}_{n}</math> विषम के लिए रिक्त है <math>n</math>.
+हम तुल्यता संबंध को परिभाषित कर सकते हैं डाइक लैंग्वेज <math>L</math> पर <math>\mathcal{D}</math> है। <math>u,v\in\mathcal{D}</math> के लिए अपने पास <math>(u,v)\in L</math> यदि और केवल <math>|u| = |v|</math> है, अर्थात <math>u</math> और <math>v</math> की लंबाई समान है। यह संबंध डाइक लैंग्वेज को विभाजित करता है: <math>\mathcal{D} / L = \{\mathcal{D}_0,\mathcal{D}_1,\ldots\}</math> अपने पास <math>\mathcal{D} = \mathcal{D}_{0} \cup \mathcal{D}_{2} \cup \mathcal{D}_{4} \cup \ldots = \bigcup_{n=0}^{\infty} \mathcal{D}_{n}</math> है। जहाँ <math>\mathcal{D}_{n} = \{ u\in\mathcal{D} \mid |u| = n\}</math> है। ध्यान दें कि <math>\mathcal{D}_{n}</math> विषम <math>n</math> के लिए रिक्त है।
-लंबाई के डाइक शब्दों का परिचय देते हुए <math>n</math>, हम उन पर  रिश्ता पेश कर सकते हैं। हर के लिए <math>n \in \mathbb{N}</math> हम  रिश्ते को परिभाषित करते हैं <math>S_{n}</math> पर <math>\mathcal{D}_{n}</math>; के लिए <math>u,v\in\mathcal{D}_{n}</math> अपने पास <math>(u,v)\in S_{n}</math> अगर और केवल अगर <math>v</math> से पहुंचा जा सकता है <math>u</math> उचित अदला-बदली की  श्रृंखला द्वारा।  शब्द में उचित अदला-बदली <math>u\in\mathcal{D}_{n}</math> '][' की घटना को '[]' से बदल देता है।
+लंबाई के डाइक शब्दों का परिचय देते हुए <math>n</math>, हम उन पर संबंध प्रस्तुत कर सकते हैं। प्रत्येक <math>n \in \mathbb{N}</math> के लिए हम संबंध <math>S_{n}</math>पर <math>\mathcal{D}_{n}</math>को परिभाषित करते हैं; <math>u,v\in\mathcal{D}_{n}</math> के लिए अपने पास <math>(u,v)\in S_{n}</math> यदि और केवल <math>v</math> से <math>u</math> '''उचित स्वैप''' की श्रृंखला द्वारा पहुंचा जा सकता है। शब्द में उचित स्वैप <math>u\in\mathcal{D}_{n}</math> '][' की घटना को '[]' से परिवर्तित कर देता है। प्रत्येक  <math>n\in\mathbb{N}</math> के लिए संबंध <math>S_{n}</math> बनाता है <math>\mathcal{D}_{n}</math> आंशिक रूप से क्रमित किए गए समुच्चय में है। संबंध <math>S_{n}</math> प्रतिवर्ती संबंध है क्योंकि उचित स्वैप का रिक्त अनुक्रम <math>u</math> को <math>u</math> होता है। सकर्मक संबंध इस प्रकार है क्योंकि हम उचित स्वैप के अनुक्रम <math>u</math> को <math>v</math> का विस्तार कर सकते हैं इसे उचित स्वैप के अनुक्रम के साथ जोड़कर <math>v</math> को <math>w</math> अनुक्रम बनाना जो <math>u</math> में <math>w</math> लेता है। उसे देखने के लिए <math>S_{n}</math> भी [[एंटीसिमेट्रिक संबंध]] है, हम सहायक फलन <math>\sigma_{n}:\mathcal{D}_{n}\rightarrow\mathbb{N}</math> का परिचय देते हैं सभी उपसर्गों के योग के रूप में <math>v</math> का <math>u</math> परिभाषित किया गया है:
-प्रत्येक के लिए <math>n\in\mathbb{N}</math> रिश्ता <math>S_{n}</math> बनाता है <math>\mathcal{D}_{n}</math> आंशिक रूप से ऑर्डर किए गए सेट में। रिश्ता <math>S_{n}</math> प्रतिवर्ती संबंध है क्योंकि उचित स्वैप का  खाली अनुक्रम लेता है <math>u</math> को <math>u</math>. सकर्मक संबंध इस प्रकार है क्योंकि हम उचित स्वैप के अनुक्रम का विस्तार कर सकते हैं <math>u</math> को <math>v</math> इसे उचित स्वैप के अनुक्रम के साथ जोड़कर <math>v</math> को <math>w</math>  अनुक्रम बनाना जो लेता है <math>u</math> में <math>w</math>. उसे देखने के लिए <math>S_{n}</math> यह [[एंटीसिमेट्रिक संबंध]] भी है, हम  सहायक फ़ंक्शन का परिचय देते हैं <math>\sigma_{n}:\mathcal{D}_{n}\rightarrow\mathbb{N}</math> सभी उपसर्गों के योग के रूप में परिभाषित <math>v</math> का <math>u</math>:
+<nowiki>:</nowiki>
 : <math>\sigma_n(u) = \sum_{vw=u} \Big( (\text{count of ['s in } v) - (\text{count of ]'s in } v) \Big)</math>
-निम्न तालिका इसे दर्शाती है <math>\sigma_{n}</math> उचित स्वैप के संबंध में [[मोनोटोनिक फ़ंक्शन]] है।
+निम्न तालिका इसे दर्शाती है <math>\sigma_{n}</math> उचित स्वैप के संबंध में [[मोनोटोनिक फ़ंक्शन|मोनोटोनिक फलन]] है।
-{| border="1" class="wikitable"
+{| class="wikitable" border="1"
-|+ Strict monotonicity of <math>\sigma_{n}</math>
+|+ <math>\sigma_{n}</math> का स्ट्रिक्ट मोनोटोनिसिटी
 |-
-! partial sums of <math>\sigma_{n}(u)</math>
+! <math>\sigma_{n}(u)</math> का आंशिक योग
 | <math>P</math> || <math>P-1</math> || <math>P</math> || <math>Q</math>
 |-
@@ Line 71: / Line 68: @@
 | <math>\ldots</math> || [ || ] || <math>\ldots</math>
 |-
-! partial sums of <math>\sigma_{n}(u')</math>
+! <math>\sigma_{n}(u')</math> का आंशिक योग
 | <math>P</math> || <math>P+1</math> || <math>P</math> || <math>Q</math>
 |-
-! Difference of partial sums
+! आंशिक योग का अंतर
 | 0 || 2 || 0 || 0
 |-
 |}
-इस तरह <math>\sigma_{n}(u') - \sigma_{n}(u) = 2 > 0</math> इसलिए <math>\sigma_{n}(u) < \sigma_{n}(u')</math> जब कोई उचित अदला-बदली होती है तो वह होता है <math>u</math> में <math>u'</math>. अब अगर हम मान लें कि दोनों <math>(u,v), (v,u)\in S_{n}</math> और <math>u\ne v</math>, तो उचित स्वैप के गैर-रिक्त अनुक्रम होते हैं <math>u</math> में लिया जाता है <math>v</math> और इसके विपरीत। परन्तु फिर <math>\sigma_{n}(u) < \sigma_{n}(v) < \sigma_{n}(u)</math> जो कि निरर्थक है. अत: जब भी दोनों <math>(u,v)</math> और <math>(v,u)</math> में हैं <math>S_{n}</math>, अपने पास <math>u = v</math>, इस तरह <math>S_{n}</math> एंटीसिमेट्रिक है.
+इस प्रकार <math>\sigma_{n}(u') - \sigma_{n}(u) = 2 > 0</math> इसलिए <math>\sigma_{n}(u) < \sigma_{n}(u')</math> जब कोई उचित परिवर्तन होता है तो वह <math>u</math> में <math>u'</math> होता है। अब यदि हम मान लें कि दोनों <math>(u,v), (v,u)\in S_{n}</math> और <math>u\ne v</math>, तो उचित स्वैप के गैर-रिक्त अनुक्रम होते हैं <math>u</math> में <math>v</math> लिया जाता है और इसके विपरीत है। परन्तु फिर <math>\sigma_{n}(u) < \sigma_{n}(v) < \sigma_{n}(u)</math> जो कि निरर्थक है। अत: जब भी दोनों <math>(u,v)</math> और <math>(v,u)</math> में हैं <math>S_{n}</math>, हमारे पास <math>u = v</math> है, इस प्रकार <math>S_{n}</math> एंटीसिमेट्रिक है।
-आंशिक आदेशित सेट <math>D_{8}</math> यदि हम [ऊपर जाने के रूप में और] नीचे जाने के रूप में व्याख्या करते हैं तो इसे परिचय के साथ दिए गए चित्रण में दिखाया गया है।
+आंशिक आदेशित समुच्चय <math>D_{8}</math> यदि हम [ऊपर जाने के रूप में और] नीचे जाने के रूप में व्याख्या करते हैं तो इसे परिचय के साथ दिए गए चित्रण में दिखाया गया है।
 == सामान्यीकरण ==
-कई सीमांककों के साथ डाइक लैंग्वेज के भिन्न रूप मौजूद हैं, उदाहरण के लिए, वर्णमाला पर D2 ( , ) , [ , और ] । ऐसी लैंग्वेज के शब्द वे होते हैं जो सभी सीमांककों के लिए अच्छी तरह से कोष्ठक में होते हैं, यानी, कोई शब्द को बाएं से दाएं पढ़ सकता है, प्रत्येक प्रारंभिक सीमांकक को स्टैक पर धकेल सकता है, और जब भी हम  समापन सीमांकक तक पहुंचते हैं तो हमें सक्षम होना चाहिए स्टैक के शीर्ष से मेल खाने वाले ओपनिंग डिलीमीटर को पॉप करने के लिए। (उपरोक्त गणना एल्गोरिथ्म सामान्यीकरण नहीं करता है)।
+कई सीमांककों के साथ डाइक लैंग्वेज के भिन्न रूप उपस्थित हैं, उदाहरण के लिए, वर्णमाला "(", ")", "[", और "]" पर D2 है। ऐसी लैंग्वेज के शब्द वे होते हैं जो सभी सीमांककों के लिए उचित प्रकार से कोष्ठक में होते हैं, अर्थात, कोई शब्द को बाएं से दाएं पढ़ सकता है, स्टैक पर प्रत्येक ओपनिंग डिलीमीटर को पुश कर सकता है, और जब भी हम क्लोजिंग डिलीमीटर पर पहुंचते हैं तो हमें स्टैक के शीर्ष से युग्मित होने वाले ओपनिंग डिलीमीटर को पॉप करने में सक्षम होना चाहिए। (उपरोक्त गणना एल्गोरिथ्म सामान्यीकरण नहीं करता है)।
 ==यह भी देखें==
 * [[डाइक सर्वांगसमता]]
-* जाली शब्द
+* लैटिस शब्द
 ==टिप्पणियाँ==
 {{reflist}}
 ==संदर्भ==
 * {{planetmath|dycklanguage}}
 * [https://arxiv.org/abs/math/0601061 A proof of the Chomsky Schützenberger theorem]
-* [https://blogs.ams.org/visualinsight/2015/07/15/dyck-words/ An AMS blog entry on Dyck words][[Category: औपचारिक भाषाएँ]]
+* [https://blogs.ams.org/visualinsight/2015/07/15/dyck-words/ An AMS blog entry on Dyck words]
-[[Category: Machine Translated Page]]
 [[Category:Created On 27/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:औपचारिक भाषाएँ]]

Anonymous

Search

डाइक लैंग्वेज: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:15, 22 August 2023

Contents

औपचारिक परिभाषा

वैकल्पिक परिभाषा

गुण

उदाहरण

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डाइक लैंग्वेज: Difference between revisions

Latest revision as of 10:15, 22 August 2023

औपचारिक परिभाषा

वैकल्पिक परिभाषा

गुण

उदाहरण

सामान्यीकरण

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories