मुक्त मोनोइड

अमूर्त बीजगणित में, एक समुच्चय पर मुक्त मोनोइड वह मोनोइड होता है जिसके तत्व उस समुच्चय से शून्य या अधिक तत्वों के सभी परिमित अनुक्रम (या स्ट्रिंग) होते हैं, स्ट्रिंग संयोजन के साथ मोनोइड ऑपरेशन के रूप में और शून्य तत्वों के अद्वितीय अनुक्रम के साथ, प्रायः रिक्त स्ट्रिंग कहा जाता है और पहचान तत्व के रूप में ε या λ द्वारा दर्शाया जाता है।I A पर मुक्त अर्धसमूह A का उपसमूह है जिसमें रिक्त स्ट्रिंग को छोड़कर सभी तत्व सम्मिलित हैं। इसे साधारणतया ए द्वारा निरूपित किया जाता है⁺.सामान्य तौर पर , अमूर्त मोनोइड या सेमीग्रुप एस को 'मुक्त' के रूप में वर्णित किया जाता है यदि यह किसी समुच्चय पर मुक्त मोनोइड (या सेमीग्रुप) के लिए समरूप है।

जैसा कि नाम से पता चलता है, मुक्त मोनोइड्स और सेमीग्रुप्स वे वस्तुएं हैं जो मोनोइड्स और सेमीग्रुप्स की संबंधित श्रेणी (गणित) में मुक्त वस्तुओं को परिभाषित करने वाली सामान्य सार्वभौमिक संपत्ति को संतुष्ट करती हैं। यह इस प्रकार है कि प्रत्येक मोनोइड मुक्त मोनोइड की एक होमोमोर्फिक छवि के रूप में उत्पन्न होता है। मुक्त अर्धसमूहों की छवियों के रूप में अर्धसमूहों के अध्ययन को संयोजी अर्धसमूह सिद्धांत कहा जाता है।

नि: शुल्क मोनोइड्स परिभाषा के अनुसार सहयोगी हैं; अर्थात् वे समूहीकरण या संचालन के क्रम को दिखाने के लिए बिना किसी कोष्ठक के लिखे गए हैं। गैर-सहयोगी समतुल्य मुक्त मैग्मा है।

उदाहरण

प्राकृतिक संख्या

मोनोइड (N₀,+) प्राकृतिक संख्याओं के अतिरिक्त सिंगलटन मुक्त जनरेटर पर एक मुक्त मोनोइड हैI इस मामले में प्राकृतिक संख्या 1 औपचारिक परिभाषा के अनुसार इस मोनॉइड में 1 , 1+1 , 1+1+1 , 1+1+1+1 जैसे सभी अनुक्रम सम्मिलित हैंI इसी तरह, रिक्त अनुक्रम सहित। ऐसे प्रत्येक अनुक्रम को उसके मूल्यांकन परिणाम से मैप करना चाहिएI शून्य के लिए रिक्त अनुक्रम ऐसे अनुक्रमों के समुच्चय से N₀ तक समरूपता स्थापित करता हैI यह समरूपता + के साथ संगत है, अर्थात किन्हीं भी दो अनुक्रमों s और t के लिए यदि s को किसी संख्या m और t' पर मैप किया गया हैI

क्लेन स्टार

औपचारिक भाषा सिद्धांत में, सामान्य तौर पर प्रतीक A का एक सीमित समुच्चय माना जाता है। प्रतीकों के एक परिमित अनुक्रम को ए पर एक शब्द कहा जाता है, और मुक्त मोनोइड ए^∗ को ए कहा जाता है। इस प्रकार, औपचारिक भाषाओं के अमूर्त अध्ययन को अंतिम रूप से उत्पन्न मुक्त मोनोइड्स के सबसमुच्चय के अध्ययन के रूप में माना जा सकता है।

उदाहरण के लिए, अक्षर A = {a, b, c}, का क्लेन स्टार A^∗ में a, b और C के सभी संयोजन सम्मिलित हैंI

यदि ए कोई समुच्चय है, तो शब्द की लंबाई ए पर कार्य करती हैI ए से अद्वितीय मोनोइड समरूपता है^∗ से (एन₀,+) जो ए के प्रत्येक तत्व को 1 से मैप करता है। मुक्त मोनॉयड इस प्रकार ग्रेडेड मोनॉयड है। (एक वर्गीकृत मोनोइड एम मोनोइड है जिसे लिखा जा सकता है $M=M_{0}\oplus M_{1}\oplus M_{2}\cdots$. प्रत्येक $M_{n}$ एक ग्रेड है; यहाँ ग्रेडिंग सिर्फ स्ट्रिंग की लंबाई है। वह है, $M_{n}$ लंबाई के वे तार हैं $n.$ $\oplus$ h> सामान्य तौर पर, समुच्चय यूनियन्स मोनोइड्स नहीं हो सकते हैं इसलिए अलग प्रतीक का उपयोग किया जाता है। ग्रेडेशन हमेशा के $\oplus$ प्रतीक।साथ लिखे जाते हैं I

सेमीग्रुप्स के सिद्धांत और ऑटोमेटा सिद्धांत के बीच गहरे संबंध हैं। उदाहरण के लिए प्रत्येक औपचारिक भाषा में एक वाक्यात्मक मोनोइड होता है जो उस भाषा को पहचानता है। नियमित भाषा के मामले में, वह मोनॉयड कुछ नियतात्मक परिमित ऑटोमेटन के सेमीऑटोमेटन से जुड़े मोनोइड के लिए आइसोमोर्फिक है जो उस भाषा को पहचानता है। एक वर्णमाला ए पर नियमित भाषाएं ए * के परिमित उपसमुच्चय को बंद कर रही हैं, संघ, उत्पाद और सबमोनॉयड के तहत ए पर मुक्त मोनॉयड। समवर्ती संगणना अर्थात् लॉक कंप्यूटर विज्ञान, म्युटेक्स या धागा जुड़ना के साथ सिस्टम, संगणना को इतिहास मोनोइड और ट्रेस मोनोइड के साथ वर्णित किया जा सकता है। मोटे तौर पर मोनॉइड के तत्व कम्यूट कर सकते हैं जैसे कि अलग-अलग थ्रेड्स किसी भी क्रम में निष्पादित हो सकते हैं लेकिन केवल एक लॉक या म्यूटेक्स तक, जो आगे कम्यूटेशन को रोकता है उस थ्रेड एक्सेस को क्रमबद्ध करें।

संयुग्मित शब्द

समविभाज्यता के पहले मामले के लिए उदाहरण: m= UNCLE , n= ANLY , p= UN , q= सफाई से , और s= CLE

एमें शब्दों की एक जोड़ी को परिभाषित करते हैं^∗ रूप uv और vu 'संयुग्म' के रूप में: एक शब्द के संयुग्मन इस प्रकार इसके वृत्ताकार बदलाव हैं। इस अर्थ में दो शब्द संयुग्मित हैं यदि वे ए द्वारा उत्पन्न मुक्त समूह के तत्वों के रूप में संयुग्मन (समूह सिद्धांत) हैं।

समानता

एक मुक्त मोनोइड समविभाज्य है: यदि समीकरण mn = pq धारण करता है, तो एक s मौजूद है जैसे कि m = ps, sn' ' = q (उदाहरण छवि देखें) या ms = p, n = sq. इस परिणाम को लेवी की लेम्मा के रूप में भी जाना जाता है। एक मोनोइड मुक्त है अगर और केवल अगर यह वर्गीकृत और समविभाज्य है।

रैंक

समुच्चय ए के सदस्यों को ए के लिए 'फ्री जेनरेटर' कहा जाता है^∗ और ए⁺. सुपरस्क्रिप्ट * को क्लेन स्टार समझा जाता है। सामान्य तौर पर यदि एस अमूर्त मुक्त मोनॉयड सेमीग्रुप है तो तत्वों का समुच्चय जो आइसोमोर्फिज्म के तहत एकल-अक्षर वाले शब्दों के समुच्चय पर सेमीग्रुप ए के लिए मैप करता है।

प्रत्येक मुक्त सेमीग्रुप या मोनॉयड एस में जनरेटर का समुच्चय होता है जिसकी प्रमुखता को एस की रैंक कहा जाता है।

दो मुक्त मोनोइड्स या सेमीग्रुप आइसोमोर्फिक हैं यदि और केवल यदि उनके पास समान रैंक है। वास्तव में सेमीग्रुप या मोनॉयड एस के लिए जनरेटर के प्रत्येक समुच्चय में जनरेटर होते हैंI जनरेटर की शब्द

लंबाई 1 होती है और इसलिए इसे केवल स्वयं ही उत्पन्न किया जा सकता है। यह इस प्रकार है कि एक मुक्त सेमिग्रुप या मोनॉयड निश्चित रूप से उत्पन्न होता है यदि और केवल अगर इसकी सीमित रैंक है।

ए का सब मोनोइड एन^∗ स्थिर होता हैI . ए का एक सबमोनॉयड^∗ स्थिर हैIउदाहरण के लिए, अंश के समुच्चय {0, 1} को ए के रूप में उपयोग करते हुए, 1 एस की सम संख्या वाली सभी बिट स्ट्रिंग्स का समुच्चय एन एक स्थिर सबमोनॉइड है क्योंकि यदि यू में 1 एस की सम संख्या है और यूएक्स भी है, तब एक्स में 1 एस की सम संख्या भी होनी चाहिए। जबकि एन को एकल बिट्स के किसी भी समुच्चय द्वारा स्वतंत्र रूप से उत्पन्न नहीं किया जा सकता हैI यह बिट स्ट्रिंग्स {0, 11, 101, 1001, 10001 } के समुच्चय द्वारा स्वतंत्र रूप से उत्पन्न किया जा सकता है -

कोड

मुक्त मोनॉइड पी के लिए मुफ्त जनरेटर का एक समुच्चय 'पी' के लिए 'आधार' के रूप में संदर्भित किया जाता है: शब्दों का एक समुच्चय सी एक 'कोड' है यदि सी * एक मुक्त मोनॉयड है और सी एक आधार है। ए में शब्दों का एक समुच्चय एक्स^∗ एक उपसर्ग है, या उसके पास उपसर्ग गुण है, यदि उसमें इसके किसी भी तत्व का उचित उपसर्ग (कंप्यूटर विज्ञान)|(स्ट्रिंग) उपसर्ग नहीं है. ए में हर उपसर्ग⁺ एक कोड है, वास्तव में एक उपसर्ग कोड है। ए का एक सबमोनॉइड एन^∗ सही एकात्मक है अगर x, xy में N का अर्थ y से N में है। सबमोनॉयड उपसर्ग द्वारा उत्पन्न होता है यदि और केवल अगर यह सही एकात्मक है।

गुणनखंड

Main article: Monoid factorisation

एक मुक्त मोनॉइड का गुणनखंड संपत्ति के साथ शब्दों के सबसमुच्चय का क्रम है कि मुक्त मोनॉइड में प्रत्येक शब्द को उपसमुच्चय से खींचे गए तत्वों के संयोजन के रूप में लिखा जा सकता है। चेन-फॉक्स-लिंडन प्रमेय कहता है कि लिंडन शब्द एक गुणनखंड प्रस्तुत करते हैं। हॉल शब्द एक गुणनखंड प्रदान करते हैंI लिंडन शब्द हॉल शब्दों का विशेष मामला है।

मुक्त पतवार

एस मुक्त मोनॉइड ए का एक उपसमुच्चय है, तो ए युक्त एस के सभी मुक्त सबमोनॉयड्स का प्रतिच्छेदन अच्छी तरह से परिभाषित है क्योंकि ए स्वयं मुक्त है और इसमें एस सम्मिलित हैI यह एक मुक्त मोनोइड है और इसे एस का 'मुक्त पतवार' कहा जाता है। इस चौराहे का आधार एक कोड है।

'दोष प्रमेय' बताता है कि यदि X परिमित है और C, X के मुक्त पतवार का आधार है, तो या तो X एक कोड है और C = X, या|सी| ≤ |एक्स| - 1।

आकारिकी

एक मुक्त मोनोइड बी से एक मोनोइड आकारिकी एफ^∗ मोनोइड एम के लिए जैसे कि f(xy) = f(x)⋅f(y) शब्दों के लिए x,y और f(ε) = ι एक नक्शा है जहां ε और ι के पहचान तत्वों को दर्शाता हैI बी^∗ और एम , क्रमशः। मोर्फिज्म एफ बी के अक्षरों पर इसके मूल्यों द्वारा निर्धारित किया जाता है और इसके विपरीत बी से एम तक एक मोर्फिज्म है। मुक्त मोनॉइड बी से एक आकारिकी f^∗ एक मुक्त मोनोइड ए के लिए^∗ कुल है यदि A का प्रत्येक अक्षर एफ की छवि में किसी शब्द में आता हैI चक्रीयया आवधिक अगर एफ की छवि {डब्लू } में समाहित है^∗ ए के कुछ शब्द डब्लू के लिए^∗. यदि लंबाई |एफ (a)| है तो आकारिकी एफ 'k-वर्दी' है A में सभी a के लिए स्थिर और k के बराबर है। मुक्त मोनॉइड B से आकारिकी f^∗ मुक्त मोनोइड ए के लिए^∗ सरल है अगर 'बी' की तुलना में कार्डिनैलिटी का अक्षर 'सी' है, तो आकारिकी एफ कारक सी के माध्यम से अर्थात यह B से आकारिकी का संघटन हैI आकृतिवाद एफ एक 'कोड' है यदि एफ के अंतर्गत अक्षर बी की एक कोड हैI प्रत्येक प्रारंभिक आकारिकी एक कोड है।

टेस्ट समुच्चय

एल के लिए बी का एक सबसमुच्चय^∗, L का परिमित उपसमुच्चय T, L के लिए एक परीक्षण समुच्चय है, यदि आकारिकी f और g पर B^∗ L पर सहमत हैं यदि और केवल यदि वे T पर सहमत हैं। 'Ehrenfeucht conjecture' यह है कि किसी भी उपसमुच्चय L का एक परीक्षण समुच्चय है: यह साबित हो गया है स्वतंत्र रूप से अल्बर्ट और लॉरेंस द्वारा; मैकनॉटन; और गुबा। सबूत हिल्बर्ट के आधार प्रमेय पर भरोसा करते हैं।

नक्शा और तह

एक मोनोइड मोर्फिज्म का कम्प्यूटेशनल अवतार एक नक्शा (उच्च-क्रम फ़ंक्शन) है जिसके बाद एक तह (उच्च-क्रम फ़ंक्शन) होता है। इस समुच्चयिंग में, समुच्चय ए पर मुक्त मोनॉयड बाइनरी ऑपरेशन के रूप में संयोजन के साथ ए से तत्वों की सूची (कंप्यूटिंग) से मेल खाता है। मुक्त मोनोइड से किसी भी अन्य मोनोइड (एम, •) के लिए एक मोनोइड समरूपता एक ऐसा कार्य है जो एफ है

• एफ (एक्स₁...एक्स_n) = एफ (एक्स₁) • ... • एफ (एक्स_n)
• एफ () = ई

जहां ई एम पर पहचान है। कम्प्यूटेशनल रूप से, इस तरह के प्रत्येक समरूपता सूची के सभी तत्वों के लिए एफ लागू करने वाले मानचित्र (उच्च-क्रम फ़ंक्शन) ऑपरेशन से मेल खाती है, जिसके बाद एक फोल्ड (उच्च-क्रम फ़ंक्शन) ऑपरेशन होता है जो परिणाम का उपयोग करके जोड़ता है बाइनरी ऑपरेटर •। यह squiggol (जिसे गैर-सहयोगी बाइनरी ऑपरेटरों के लिए सामान्यीकृत किया जा सकता है) ने MapReduce सॉफ़्टवेयर ढांचे को प्रेरित किया है।

एंडोमोर्फिज्म

ए का एक एंडोमोर्फिज्म^∗ A का आकार है^∗ खुद के लिए। पहचान मानचित्र I, A का एंडोमोर्फिज्म है^∗, और एंडोमोर्फिज्म कार्यों की संरचना के तहत एक मोनोइड बनाते हैं।

एक एंडोमोर्फिज्म f 'लम्बी' है यदि कोई अक्षर ऐसा है कि f(a) = गैर-रिक्त स्ट्रिंग s के लिए।

स्ट्रिंग प्रोजेक्शन

स्ट्रिंग ऑपरेशंस का संचालन # स्ट्रिंग प्रोजेक्शन एक एंडोमोर्फिज्म है। अर्थात्, एक अक्षर a ∈ Σ और एक स्ट्रिंग s ∈ Σ दिया गया है^∗, स्ट्रिंग प्रोजेक्शन पी_a(एस) एस से ए की हर घटना को हटा देता है; इसे औपचारिक रूप से परिभाषित किया गया है

$p_{a}(s)={\begin{cases}\varepsilon &{\text{if }}s=\varepsilon ,{\text{ the empty string}}\\p_{a}(t)&{\text{if }}s=ta\\p_{a}(t)b&{\text{if }}s=tb{\text{ and }}b\neq a.\end{cases}}$

ध्यान दें कि स्ट्रिंग प्रोजेक्शन अच्छी तरह से परिभाषित है, भले ही मोनॉइड का रैंक अनंत हो, क्योंकि उपरोक्त पुनरावर्ती परिभाषा परिमित लंबाई के सभी तारों के लिए काम करती है। स्ट्रिंग प्रोजेक्शन मुक्त मोनोइड्स की श्रेणी में एक रूपवाद है, ताकि

$p_{a}\left(\Sigma ^{*}\right)=\left(\Sigma -a\right)^{*}$

कहाँ $p_{a}\left(\Sigma ^{*}\right)$ समझा जाता है कि सभी परिमित तारों का मुक्त मोनॉइड होता है जिसमें अक्षर a नहीं होता है। प्रोजेक्शन स्ट्रिंग कॉन्सटेनेशन के संचालन के साथ शुरू होता है, ताकि $p_{a}(st)=p_{a}(s)p_{a}(t)$ सभी तार एस और टी के लिए। स्ट्रिंग प्रोजेक्शन के कई सही व्युत्क्रम हैं, और इस प्रकार यह एक विभाजित एपिमोर्फिज्म है।

पहचान रूपवाद है $p_{\varepsilon },$ के रूप में परिभाषित $p_{\varepsilon }(s)=s$ सभी स्ट्रिंग्स के लिए, और $p_{\varepsilon }(\varepsilon )=\varepsilon$.

स्ट्रिंग प्रोजेक्शन कम्यूटेटिव है, स्पष्ट रूप से

$p_{a}(p_{b}(s))=p_{b}(p_{a}(s)).$

परिमित रैंक के मुक्त मोनोइड्स के लिए, यह इस तथ्य से अनुसरण करता है कि एक ही रैंक के मुक्त मोनोइड्स आइसोमोर्फिक हैं, क्योंकि प्रक्षेपण मोनोइड के रैंक को एक से कम कर देता है।

स्ट्रिंग प्रोजेक्शन बेवकूफ है, जैसा

$p_{a}(p_{a}(s))=p_{a}(s)$

सभी तार एस के लिए। इस प्रकार, प्रक्षेपण एक उदासीन, क्रमविनिमेय संक्रिया है, और इसलिए यह एक बंधी हुई अर्धजालिका या एक क्रमविनिमेय बैंड (बीजगणित) बनाता है।

मुफ्त क्रमविनिमेय मोनोइड

एक समुच्चय ए को देखते हुए, ए पर 'फ्री कम्यूटेटिव मोनोइड' ए से तैयार किए गए तत्वों के साथ सभी परिमित multiset ्स का समुच्चय है, जिसमें मोनोइड ऑपरेशन मल्टीसमुच्चय योग है और मोनोइड यूनिट रिक्त मल्टीसमुच्चय है।

उदाहरण के लिए, यदि ए = {ए, बी, सी}, ए पर मुक्त कम्यूटेटिव मोनोइड के तत्व फॉर्म के हैं

{ε, ए, एबी, ए^{2</सुप>बी, अब3सी4, ...}.}

अंकगणित के मौलिक प्रमेय में कहा गया है कि गुणन के तहत धनात्मक पूर्णांकों का मोनॉयड जनरेटर के अनंत समुच्चय पर एक मुक्त क्रमविनिमेय मोनॉइड है, अभाज्य संख्याएँ।

फ्री कम्यूटेटिव सेमीग्रुप मुक्त आंशिक रूप से विनिमेय मोनॉयड सबसमुच्चय है जिसमें रिक्त मल्टीसमुच्चय को छोड़कर 'ए' से खींचे गए सभी मल्टीसमुच्चय सम्मिलित हैं।

मुक्त आंशिक रूप से कम्यूटेटिव मोनॉयड, या 'ट्रेस मोनॉयड', एक सामान्यीकरण है जिसमें उदाहरण के रूप में फ्री और फ्री कम्यूटेटिव मोनॉयड दोनों सम्मिलित हैं। यह सामान्यीकरण साहचर्य और कंप्यूटर विज्ञान में समांतर कंप्यूटिंग के अध्ययन में अनुप्रयोगों को ढूंढता है।

यह भी देखें

• स्ट्रिंग ऑपरेशंस

संदर्भ

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 978-0-521-82332-6, Zbl 1086.11015
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010), Codes and automata, Encyclopedia of Mathematics and its Applications, vol. 129, Cambridge: Cambridge University Press, ISBN 978-0-521-88831-8, Zbl 1187.94001
• Lothaire, M. (1997), Combinatorics on words, Cambridge Mathematical Library, vol. 17, Contributors: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R. Series editors: Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, doi:10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
• Lothaire, M. (2005), Applied combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 105, A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, Cambridge: Cambridge University Press, ISBN 0-521-84802-4, Zbl 1133.68067
• Pytheas Fogg, N. (2002), Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.), Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Berlin: Springer-Verlag, ISBN 3-540-44141-7, Zbl 1014.11015
• Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge: Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177
• Salomaa, Arto (1981), Jewels of Formal Language Theory, Pitman Publishing, ISBN 0-273-08522-0, Zbl 0487.68064

बाहरी संबंध

• Media related to मुक्त मोनोइड at Wikimedia Commons