डाइक लैंग्वेज

लंबाई 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 → ε | "[" S "]" S

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

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

S → ("[" 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} (])$ ऊपर वर्णित है।
• चॉम्स्की-शूट्ज़ेनबर्गर प्रतिनिधित्व प्रमेय के अनुसार, कोई भी संदर्भ-मुक्त लैंग्वेज एक या अधिक प्रकार के ब्रैकेट युग्म पर डाइक लैंग्वेज के साथ कुछ नियमित लैंग्वेज के प्रतिच्छेदन की समरूप छवि है।
• दो भिन्न-भिन्न प्रकार के ब्रैकेट वाली डाइक लैंग्वेज को समष्टिता वर्ग $TC^{0}$ में पहचाना जा सकता है।
• 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 है। ऐसी लैंग्वेज के शब्द वे होते हैं जो सभी सीमांककों के लिए उचित प्रकार से कोष्ठक में होते हैं, अर्थात, कोई शब्द को बाएं से दाएं पढ़ सकता है, स्टैक पर प्रत्येक ओपनिंग डिलीमीटर को पुश कर सकता है, और जब भी हम क्लोजिंग डिलीमीटर पर पहुंचते हैं तो हमें स्टैक के शीर्ष से युग्मित होने वाले ओपनिंग डिलीमीटर को पॉप करने में सक्षम होना चाहिए। (उपरोक्त गणना एल्गोरिथ्म सामान्यीकरण नहीं करता है)।

यह भी देखें

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

संदर्भ

• डाइक लैंग्वेज at PlanetMath.
• A proof of the Chomsky Schützenberger theorem
• An AMS blog entry on Dyck words