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

लंबाई 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 "]")^*

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

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

इसके अतिरिक्त अन्य संदर्भों में डाइक लैंग्वेज को विभाजित करके परिभाषित करना सहायक हो सकता है $\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} (])$ ऊपर वर्णित है।
• चॉम्स्की-शूट्ज़ेनबर्गर प्रतिनिधित्व प्रमेय के अनुसार, कोई भी संदर्भ-मुक्त लैंग्वेज या अधिक प्रकार के ब्रैकेट जोड़े पर डाइक लैंग्वेज के साथ कुछ नियमित लैंग्वेज के प्रतिच्छेदन की समरूप छवि है।
• दो अलग-अलग प्रकार के ब्रैकेट वाली डाइक लैंग्वेज को जटिलता वर्ग TC0| में पहचाना जा सकता है$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}$ उचित स्वैप के संबंध में मोनोटोनिक फ़ंक्शन है।

Strict monotonicity of $\sigma _{n}$

partial sums of $\sigma _{n}(u)$	$P$	$P-1$	$P$	$Q$
$u$	$\ldots$	]	[	$\ldots$
$u'$	$\ldots$	[	]	$\ldots$
partial sums of $\sigma _{n}(u')$	$P$	$P+1$	$P$	$Q$
Difference of partial sums	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