मुक्त मोनोइड

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

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

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

उदाहरण

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

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

क्लेन स्टार

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

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

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

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

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

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

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

समानता

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

एक मोनोइड मुक्त है अगर और केवल अगर यह वर्गीकृत और समविभाज्य है।

रैंक

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

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

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

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

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

कोड

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

A का एक सबमोनॉइड एन^∗ सही एकात्मक है अगर x, xy में N का अर्थ y से N में है। सबमोनॉयड उपसर्ग द्वारा उत्पन्न होता है यदि और केवल अगर यह सही एकात्मक है।

गुणनखंड

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

मुक्त पतवार

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

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

आकारिकी

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

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

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

मानचित्र और तह

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

• F (X₁...X_n) = F (X₁) • ... • F (X_n)
• F () = ई

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

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

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

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

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

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

$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)$ सभी तार S और T के लिए है। स्ट्रिंग प्रोजेक्शन के कई सही व्युत्क्रम हैं, और इस प्रकार यह एक विभाजित एपिमोर्फिज्म है।

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

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

${}_{}$