क्लेन बीजगणित: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
साहित्य में क्लेन बीजगणित और संबंधित संरचनाओं की विभिन्न असमान परिभाषाएं दी गई हैं।<ref>For a survey, see: {{cite book | zbl=0732.03047 | last=Kozen | first=Dexter | chapter=On Kleene algebras and closed semirings | title=Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990 | series=Lecture Notes Computer Science | volume=452 | pages=26–47 | year=1990 | author-link=Dexter Kozen | editor1-last=Rovan | editor1-first=Branislav | publisher=[[Springer-Verlag]] | chapter-url=http://ecommons.library.cornell.edu/bitstream/1813/6971/1/90-1131.pdf }}</ref> यहां हम वह परिभाषा देते है जो आजकल सबसे सामान्य लगती है। | साहित्य में क्लेन बीजगणित और संबंधित संरचनाओं की विभिन्न असमान परिभाषाएं दी गई हैं।<ref>For a survey, see: {{cite book | zbl=0732.03047 | last=Kozen | first=Dexter | chapter=On Kleene algebras and closed semirings | title=Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990 | series=Lecture Notes Computer Science | volume=452 | pages=26–47 | year=1990 | author-link=Dexter Kozen | editor1-last=Rovan | editor1-first=Branislav | publisher=[[Springer-Verlag]] | chapter-url=http://ecommons.library.cornell.edu/bitstream/1813/6971/1/90-1131.pdf }}</ref> यहां हम वह परिभाषा देते है जो आजकल सबसे सामान्य लगती है। | ||
क्लेन बीजगणित समुच्चय (गणित) A है जो दो बाइनरी संक्रियाओं के साथ + : | क्लेन बीजगणित समुच्चय (गणित) A है जो दो बाइनरी संक्रियाओं के साथ + : ''A'' × ''A'' → ''A'' और · : ''A'' × ''A'' → ''A'' और फलन <sup>*</sup> : ''A'' → ''A'' क्रमशः a + b, ab और a<sup>*</sup> के रूप में लिखा जाता है, जिससे कि निम्नलिखित स्वयंसिद्ध संतुष्ट है। | ||
* + और · की [[संबद्धता]] : | * + और · की [[संबद्धता]] : a + (b + c) = (a + b) + c और a (bc) = (ab) c A में सभी a, b, c के लिए। | ||
* + की [[क्रमविनिमेयता]] : | * + की [[क्रमविनिमेयता]] : a + b = b + a सभी a, b में A के लिए। | ||
* [[वितरण]] : ए ( | * [[वितरण]] : ए (b + c) = (ab) + (ac) और (b + c) a = (ba) + (ca) A में सभी a, b, c के लिए। | ||
* + और · के लिए [[पहचान तत्व]] : | * + और · के लिए [[पहचान तत्व]] : A में तत्व 0 उपस्तिथ होता है जैसे A में सभी के लिए: a + 0 = 0 + a = a. | ||
* | *A में अवयव 1 उपस्तिथ होता है जैसे A में सभी A के लिए : a1 = 1a = a. | ||
* | * a में सभी A के लिए 0: a0 = 0a = 0 द्वारा [[शोषक तत्व|अवशोषक तत्व]]। | ||
उपरोक्त स्वयंसिद्ध सेमिरिंग को परिभाषित करते हैं। अतः हमें और आवश्यकता होता है। | उपरोक्त स्वयंसिद्ध सेमिरिंग को परिभाषित करते हैं। अतः हमें और आवश्यकता होता है। | ||
* + उदासीन है : | * + उदासीन है : A में सभी a के लिए a + a = a. | ||
A पर आंशिक क्रम ≤ परिभाषित करना संभव होता है, अतः a ≤ b समूह करके [[अगर और केवल अगर|और]] a + b = b (या समकक्ष: a ≤ b यदि A में x उपस्तिथ होता है जैसे कि ए + एक्स = बी ; किसी भी परिभाषा के साथ, a ≤ b ≤ a का अर्थ होता है a = b)। इस क्रम से हम संक्रिया <sup>*</sup> के बारे में अंतिम चार अभिगृहीत तैयार कर सकते हैं। | |||
* 1 + | * 1 + a (a<sup>*</sup>) ≤ a<sup>*</sup> सभी के लिए A में। | ||
* 1 + ( | * 1 + (a<sup>*</sup>)a ≤ a<sup>*</sup> सभी के लिए A में। | ||
* यदि | * यदि a और x, A में ऐसे हैं कि ax ≤ x, तब a<sup>*x</sup> ≤ x | ||
* यदि | * यदि a और x, A में ऐसे हैं कि xa ≤ x, तब x(a<sup>*</sup>) ≤ x <ref>Kozen (1990), sect.2.1, p.3</ref> | ||
सामान्यतः सहज रूप से, किसी को | सामान्यतः सहज रूप से, किसी को a + b को संघ के रूप में या a और b की कम से कम ऊपरी सीमा और ab को कुछ गुणन के रूप में सोचा जाता है, जो मोनोटोनिक फ़ंक्शन क्रम सिद्धांत में होता है, इस अर्थ में कि a ≤ b का अर्थ ax ≤ bx है। इस प्रकार स्टार ऑपरेटर के पीछे का विचार यह होता है कि a<sup>*</sup> = 1 + a + aa + aaa + ... [[ प्रोग्रामिंग भाषा सिद्धांत |प्रोग्रामिंग भाषा सिद्धांत]] के दृष्टिकोण से, कोई भी + को पसंद के रूप में, · को अनुक्रमण के रूप में और <sup>*</sup> पुनरावृत्ति के रूप में व्याख्या कर सकता है। | ||
== उदाहरण == | == उदाहरण == | ||
| Line 36: | Line 36: | ||
माना Σ परिमित [[सबसेट|उपसमूह]] (वर्णमाला) हो और A को Σ पर सभी नियमित अभिव्यक्ति [[औपचारिक भाषा]] सिद्धांतों का समूह होता है। यदि वह ही औपचारिक भाषा का वर्णन करते हैं तब हम दो ऐसे नियमित भावों को समान मानते हैं। तब A क्लेन बीजगणित बनाता है। सामान्यतः यह इस अर्थ में [[मुक्त वस्तु]] क्लेन बीजगणित होती है कि नियमित अभिव्यक्तियों के मध्य कोई भी समीकरण क्लेन बीजगणित के स्वयंसिद्धों से अनुसरण करता है और इसलिए प्रत्येक क्लेन बीजगणित में मान्य होता है। | माना Σ परिमित [[सबसेट|उपसमूह]] (वर्णमाला) हो और A को Σ पर सभी नियमित अभिव्यक्ति [[औपचारिक भाषा]] सिद्धांतों का समूह होता है। यदि वह ही औपचारिक भाषा का वर्णन करते हैं तब हम दो ऐसे नियमित भावों को समान मानते हैं। तब A क्लेन बीजगणित बनाता है। सामान्यतः यह इस अर्थ में [[मुक्त वस्तु]] क्लेन बीजगणित होती है कि नियमित अभिव्यक्तियों के मध्य कोई भी समीकरण क्लेन बीजगणित के स्वयंसिद्धों से अनुसरण करता है और इसलिए प्रत्येक क्लेन बीजगणित में मान्य होता है। | ||
पुनः मान लीजिए Σ अक्षर होता है। मान लीजिए | पुनः मान लीजिए Σ अक्षर होता है। मान लीजिए A Σ पर सभी [[नियमित भाषा]]ओं का समूह होता है (या Σ पर सभी [[संदर्भ-मुक्त भाषा|संदर्भ-मुक्त भाषाओं]] का समूह होता है, या Σ पर सभी [[पुनरावर्ती भाषा|पुनरावर्ती भाषाओं]] का समूह है या Σ पर सभी भाषाओं का समूह होता है)। तब [[संघ (सेट सिद्धांत)|संघ (समूह सिद्धांत)]] (+ के रूप में लिखा जाता है) और A के दो तत्वों का संयोजन (लिखा जाता है) फिर से A से संबंधित होता है और इसलिए [[क्लेन स्टार]] ऑपरेशन A के किसी भी तत्व पर प्रयुक्त होता है। इस प्रकार हम क्लेन बीजगणित A प्राप्त करते हैं जिसमें 0 [[खाली सेट|रिक्त समूह]] होता है और 1 वह समूह होता है जिसमें केवल [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] होती है। | ||
सामान्यतः | सामान्यतः M को पहचान कर तत्व e के साथ [[मोनोइड]] होने देता है और A को M के सभी उपसमूहों का समूह होने देता है। इस प्रकार दो ऐसे उपसमूह S और T के लिए, S + T को S और T का संघ होने देता है और ST = {st: s में S समूह करना और t में T}। S<sup>*</sup> को S द्वारा उत्पन्न M के सबमोनॉइड के रूप में परिभाषित किया गया है, जिसे {e} ∪ S ∪ SS ∪ SSS ∪ ... के रूप में वर्णित किया जा सकता है ... पुनः A रिक्त बीजगणित बनाता है जिसमें 0 रिक्त समूह होता है और 1 {e} किसी भी छोटी श्रेणी के सिद्धांत के लिए समान रूप से निर्माण किया जा सकता है। | ||
इस प्रकार क्षेत्र के ऊपर इकाई बीजगणित के रैखिक उपस्थान क्लेन बीजगणित बनाते हैं। अतः रैखिक उपसमष्टियाँ | इस प्रकार क्षेत्र के ऊपर इकाई बीजगणित के रैखिक उपस्थान क्लेन बीजगणित बनाते हैं। अतः रैखिक उपसमष्टियाँ V और W को देखते हुए, V + W को दो उपसमष्टियों के योग के रूप में और 0 को तुच्छ उपसमष्टि {0} के रूप में परिभाषित करता है। परिभाषित करना {{math|1=''V'' · ''W'' = span {{mset|v · w | v ∈ V, w ∈ W}}}}, क्रमशः V और W से सदिश के उत्पाद की [[रैखिक अवधि]] को परिभाषित करना {{math|1=1 = span {I}<nowiki/>}}, बीजगणित की इकाई की अवधि V का बंद होना V की सभी शक्तियों के [[मॉड्यूल का प्रत्यक्ष योग]] होता है। | ||
<math display="block">V^{*} = \bigoplus_{i = 0}^{\infty} V^{i}</math> | <math display="block">V^{*} = \bigoplus_{i = 0}^{\infty} V^{i}</math> | ||
मान लीजिए कि | मान लीजिए कि M समुच्चय है और A, M पर सभी [[द्विआधारी संबंध|द्विआधारी संबंधों]] का समुच्चय होता है। इस प्रकार + होने के लिए और <sup>*</sup> [[रिफ्लेक्सिव ट्रांजिटिव क्लोजर]] हम क्लेन बीजगणित प्राप्त करते हैं। | ||
संचालन के साथ प्रत्येक [[बूलियन बीजगणित (संरचना)]] <math>\lor</math> और <math>\land</math> यदि हम उपयोग करते हैं तब यह क्लेन बीजगणित में परिवर्तित हो जाता है <math>\lor</math> + के लिए, <math>\land</math> के लिए · और समूह के लिए a<sup>*</sup> = 1 समूह करता है। | संचालन के साथ प्रत्येक [[बूलियन बीजगणित (संरचना)]] <math>\lor</math> और <math>\land</math> यदि हम उपयोग करते हैं तब यह क्लेन बीजगणित में परिवर्तित हो जाता है <math>\lor</math> + के लिए, <math>\land</math> के लिए · और समूह के लिए a<sup>*</sup> = 1 समूह करता है। | ||
फ़्लॉइड-वॉर्शल एल्गोरिथम को प्रयुक्त करने के लिए अधिक भिन्न क्लेन बीजगणित का उपयोग किया जा सकता है, क्लेन के एल्गोरिथ्म द्वारा [[ग्राफ सिद्धांत]] के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई की गणना, नियतात्मक परिमित | फ़्लॉइड-वॉर्शल एल्गोरिथम को प्रयुक्त करने के लिए अधिक भिन्न क्लेन बीजगणित का उपयोग किया जा सकता है, क्लेन के एल्गोरिथ्म द्वारा [[ग्राफ सिद्धांत]] के प्रत्येक दो शीर्षों के लिए सबसे कम पथ की लंबाई की गणना, नियतात्मक परिमित ऑटोमेटन के प्रत्येक दो राज्यों के लिए नियमित अभिव्यक्ति की गणना करता है। इस प्रकार [[विस्तारित वास्तविक संख्या रेखा]] का उपयोग करते हुए, a + b को न्यूनतम a और b और ab को a और b का सामान्य योग होने के लिए लिया जाता है (+∞ और −∞ के योग को +∞ के रूप में परिभाषित किया जा रहा है)। a<sup>*</sup> को गैर-ऋणात्मक a के लिए वास्तविक संख्या शून्य और ऋणात्मक a के लिए −∞ के रूप में परिभाषित किया गया है। यह क्लेन बीजगणित है जिसमें शून्य तत्व +∞ और तत्व वास्तविक संख्या शून्य है। इस प्रकार भारित निर्देशित ग्राफ को तब नियतात्मक परिमित ऑटोमेटन के रूप में माना जा सकता है, जिसमें प्रत्येक संक्रमण को उसके वजन द्वारा लेबल किया जाता है। अतः किसी भी दो ग्राफ नोड्स (ऑटोमेटन स्टेट्स) के लिए, क्लेन के एल्गोरिथ्म से गणना की गई नियमित अभिव्यक्ति, इस विशेष क्लेन बीजगणित में, नोड्स के मध्य सबसे छोटी पथ लंबाई का मूल्यांकन करती है।<ref>{{citation|title=Handbook of Graph Theory| series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press| year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref> | ||
== गुण == | == गुण == | ||
0 ≤ | 0 ≤ a सभी a के लिए A में शून्य सबसे छोटा अवयव होता है। | ||
योग | योग a + b, a और b की सबसे छोटी ऊपरी सीमा होती है। इस प्रकार हमारे समीप a ≤ a + b और b ≤ a + b है और यदि x, A का तत्व है जिसमें a ≤ x और b ≤ x है, तब a + b ≤ x होता है। इसी प्रकार, a<sub>1</sub> + ... + a<sub>''n''</sub> तत्वों a<sub>1</sub>, ..., a<sub>''n''</sub> का सबसे कम से कम ऊपरी सीमा है। | ||
गुणन और योग एकदिष्ट होता हैं। यदि | गुणन और योग एकदिष्ट होता हैं। यदि a ≤ b, तब | ||
* | * a + x ≤ b + x, | ||
* | * ax ≤ bx, और | ||
* | * xa ≤ xb | ||
A में सभी x के लिए। | |||
स्टार ऑपरेशन के संबंध में, हमारे समीप है। | स्टार ऑपरेशन के संबंध में, हमारे समीप है। | ||
* 0<sup>*</sup> = 1 और 1<sup>*</sup> = 1, | * 0<sup>*</sup> = 1 और 1<sup>*</sup> = 1, | ||
* | * a ≤ b का अर्थ है a<sup>*</sup> ≤ b<sup>*</sup> (एकरसता), | ||
* | * a<sup>n</sup> ≤ a<sup>*</sup> प्रत्येक प्राकृत संख्या n के लिए, a<sup>n</sup> ≤ a<sup>*</sup> जहाँ a को a के n-गुना गुणन के रूप में परिभाषित किया गया है। | ||
* ( | * (a<sup>*</sup>)(a<sup>*</sup>) = a<sup>*, | ||
* ( | * (a*)<sup>* = a<sup>* | ||