क्लेन स्टार: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Unary operation on string sets}} | {{Short description|Unary operation on string sets}} | ||
[[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में, क्लेन स्टार (या क्लेन संचालक या क्लेन क्लोजर) या यूनरी संचालन है, या तो | [[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में, क्लेन स्टार (या क्लेन संचालक या क्लेन क्लोजर) या यूनरी संचालन है, या तो [[स्ट्रिंग (कंप्यूटर विज्ञान)|श्रृंखला (कंप्यूटर विज्ञान)]] के [[सेट (गणित)|गणित)]] पर या प्रतीकों या वर्णों के समूह पर होता है। गणित में,इसे सामान्यतौर पर स्वतंत्र एकाभ निर्माण के रूप में जाना जाता है। समूह पर क्लेन स्टार का अनुप्रयोग <math>V</math> के रूप में <math>V^*</math> लिखा गया है| यह [[नियमित अभिव्यक्ति]]यों के लिए व्यापक रूप से उपयोग किया जाता है, जो संदर्भ है जिसमें [[स्टीफन क्लेन]] द्वारा इसे कुछ [[ऑटोमेटा सिद्धांत]] की विशेषता के लिए प्रस्तुत किया गया था, जहां इसका अर्थ शून्य या अत्यधिक पुनरावृति है। | ||
# यदि | # यदि <math>V</math> श्रंखला का समुच्चय है, फिर <math>V^*</math>के सबसे छोटे [[सुपरसेट|अधिसमुच्चय]] के रूप में परिभाषित किया गया है <math>V</math> जिसमें [[खाली स्ट्रिंग|रिक्त श्रृंखला]] है <math>\varepsilon</math> और संयोजन के अंतर्गत [[समापन (गणित)]] है। | ||
# यदि | # यदि <math>V</math> प्रतीकों या वर्णों का समूह है, तो रिक्त श्रंखला सहित <math>\varepsilon</math>, <math>V^*</math>में प्रतीकों पर <math>V</math> सभी श्रृंखला का समुच्चय है | | ||
समूह <math>V^*</math> रिक्त श्रंखला | समूह <math>V^*</math> रिक्त श्रंखला और सभी परिमित-लंबाई वाले श्रंखला के समूह के रूप में भी वर्णित किया जा सकता है, जो अपने ढंग से <math>V</math> तत्वों को जोड़कर उत्पन्न किया जा सकता है, एक ही तत्व को कई बार उपयोग करने की अनुमति देता है। यदि <math>V</math> या तो [[खाली सेट|रिक्त श्रंखला]] ∅ या एकल समुच्चय <math>\{\varepsilon\}</math> है, तब <math>V^{*}=\{\varepsilon\}</math> है; यदि <math>V</math> तब कोई अन्य परिमित समुच्चय या गणनीय रूप से अपरिमित समुच्चय <math>V^*</math> है, गणनीय अपरिमित समुच्चय है।<ref>{{cite web |author=Nayuki Minase |date=10 May 2011 |title=गणनीय सेट और क्लेन स्टार|work=Project Nayuki |url=http://www.nayuki.io/page/countable-sets-and-kleene-star |access-date=11 January 2012}}</ref> परिणामस्वरूप, प्रत्येक [[औपचारिक भाषा]] एक परिमित या गणनीय रूप से अनंत वर्णमाला पर <math>\Sigma</math> गणनीय है, क्योंकि यह गणनीय अपरिमित समुच्चय का उपसमुच्चय <math>\Sigma^{*}</math> है | | ||
संचालकों का उपयोग [[उत्पादक व्याकरण|प्रजनक व्याकरण]] के [[पुनर्लेखन नियम|पुनर्लेखन नियमों]] में किया जाता है। | |||
== परिभाषा और संकेतन == | == परिभाषा और संकेतन == | ||
दिए गए समूह <math>V</math> को परिभाषित करना है। | |||
परिभाषित करना | :<math>V^{0}=\{\varepsilon\}</math> (सिर्फ रिक्त श्रृंखला वाली भाषा), | ||
:<math>V^{0}=\{\varepsilon\}</math> ( | |||
:<math>V^{1}=V</math> | :<math>V^{1}=V</math> | ||
और पुनरावर्ती रूप से | और पुनरावर्ती रूप से समुच्चय को परिभाषित करें | ||
:<math>V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \}</math> प्रत्येक के लिए <math>i>0</math>. | :<math>V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \}</math> प्रत्येक के लिए <math>i>0</math>. | ||
Revision as of 12:40, 5 May 2023
गणितीय तर्क और कंप्यूटर विज्ञान में, क्लेन स्टार (या क्लेन संचालक या क्लेन क्लोजर) या यूनरी संचालन है, या तो श्रृंखला (कंप्यूटर विज्ञान) के गणित) पर या प्रतीकों या वर्णों के समूह पर होता है। गणित में,इसे सामान्यतौर पर स्वतंत्र एकाभ निर्माण के रूप में जाना जाता है। समूह पर क्लेन स्टार का अनुप्रयोग के रूप में लिखा गया है| यह नियमित अभिव्यक्तियों के लिए व्यापक रूप से उपयोग किया जाता है, जो संदर्भ है जिसमें स्टीफन क्लेन द्वारा इसे कुछ ऑटोमेटा सिद्धांत की विशेषता के लिए प्रस्तुत किया गया था, जहां इसका अर्थ शून्य या अत्यधिक पुनरावृति है।
- यदि श्रंखला का समुच्चय है, फिर के सबसे छोटे अधिसमुच्चय के रूप में परिभाषित किया गया है जिसमें रिक्त श्रृंखला है और संयोजन के अंतर्गत समापन (गणित) है।
- यदि प्रतीकों या वर्णों का समूह है, तो रिक्त श्रंखला सहित , में प्रतीकों पर सभी श्रृंखला का समुच्चय है |
समूह रिक्त श्रंखला और सभी परिमित-लंबाई वाले श्रंखला के समूह के रूप में भी वर्णित किया जा सकता है, जो अपने ढंग से तत्वों को जोड़कर उत्पन्न किया जा सकता है, एक ही तत्व को कई बार उपयोग करने की अनुमति देता है। यदि या तो रिक्त श्रंखला ∅ या एकल समुच्चय है, तब है; यदि तब कोई अन्य परिमित समुच्चय या गणनीय रूप से अपरिमित समुच्चय है, गणनीय अपरिमित समुच्चय है।[1] परिणामस्वरूप, प्रत्येक औपचारिक भाषा एक परिमित या गणनीय रूप से अनंत वर्णमाला पर गणनीय है, क्योंकि यह गणनीय अपरिमित समुच्चय का उपसमुच्चय है |
संचालकों का उपयोग प्रजनक व्याकरण के पुनर्लेखन नियमों में किया जाता है।
परिभाषा और संकेतन
दिए गए समूह को परिभाषित करना है।
- (सिर्फ रिक्त श्रृंखला वाली भाषा),
और पुनरावर्ती रूप से समुच्चय को परिभाषित करें
- प्रत्येक के लिए .
अगर एक औपचारिक भाषा है, तो , द -सेट की शक्ति , संयोजन के लिए एक आशुलिपि है # समुच्चय के तार के समुच्चय का संयोजन खुद के साथ बार। वह है,सभी स्ट्रिंग्स (कंप्यूटर साइंस) के सेट के रूप में समझा जा सकता है जिसे के संयोजन के रूप में दर्शाया जा सकता है में तार .
क्लेन स्टार ऑन की परिभाषा है[2]
इसका मतलब यह है कि क्लेन स्टार ऑपरेटर एक बेवकूफ यूनरी ऑपरेटर है: किसी भी सेट के लिए तार या वर्णों की, जैसा हरएक के लिए .
क्लीन प्लस
कुछ औपचारिक भाषा अध्ययनों में, (उदाहरण के लिए भाषाओं का सार परिवार) क्लेन स्टार ऑपरेशन पर भिन्नता जिसे क्लेन प्लस कहा जाता है, का उपयोग किया जाता है। क्लेन प्लस इसे छोड़ देता है उपरोक्त संघ में अवधि। दूसरे शब्दों में, क्लेन प्लस ऑन है
या
उदाहरण
स्ट्रिंग्स के सेट पर लागू क्लेन स्टार का उदाहरण:
- {एबी, सी}* = { ε, एबी, सी, एबीबी, एबीसी, कैब, सीसी, अबाबाब, एबीबीसी, एबीसीबी, एबीसीसी, कैबाब, कैबब, सीसीएबी, सीसीसी, ...}।
क्लेन प्लस का उदाहरण वर्णों के सेट पर लागू होता है:
- {ए, बी, सी}+ = {ए, बी, सी, एए, एबी, एसी, बीए, बीबी, बीसी, सीए, सीबी, सीसी, एएए, एएबी, ...}।
क्लेन स्टार समान वर्ण सेट पर लागू होता है:
- {ए, बी, सी}* = { ε, ए, बी, सी, एए, एबी, एसी, बीए, बीबी, बीसी, सीए, सीबी, सीसी, आआ, एएबी, ...}।
खाली सेट पर लागू क्लेन स्टार का उदाहरण:
- ∅*</सुप> = {ε}.
खाली सेट पर लागू क्लेन प्लस का उदाहरण:
- ∅+ = ∅ ∅* = { } = ∅,
जहां संयोजन एक साहचर्य और गैर-अनुवर्ती उत्पाद है।
खाली स्ट्रिंग वाले सिंगलटन सेट पर लागू क्लेन प्लस और क्लेन स्टार का उदाहरण:
- अगर , तब भी प्रत्येक के लिए , इस तरह .
सामान्यीकरण
स्ट्रिंग्स बाइनरी ऑपरेशन के रूप में संयोजन के साथ एक मोनोइड बनाते हैं और ε पहचान तत्व। क्लेन स्टार को किसी भी मोनोइड के लिए परिभाषित किया गया है, न कि केवल स्ट्रिंग्स के लिए। अधिक सटीक रूप से, (M, ⋅) को एक मोनोइड होने दें, और S ⊆ M. फिर S* M युक्त S का सबसे छोटा उपमोनाइड है; यानी एस* में M, समुच्चय S का तटस्थ तत्व शामिल है, और ऐसा है कि यदि x,y ∈ S*, तो x⋅y ∈ S*</सुप>.
इसके अलावा, क्लेन स्टार को बीजगणितीय संरचना में *-ऑपरेशन (और संघ) को शामिल करके पूर्ण स्टार सेमिरिंग की धारणा से सामान्यीकृत किया जाता है।[4]
यह भी देखें
संदर्भ
- ↑ Nayuki Minase (10 May 2011). "गणनीय सेट और क्लेन स्टार". Project Nayuki. Retrieved 11 January 2012.
- ↑ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). असतत गणित की नींव. Brooks/Cole. p. 656. ISBN 0534923739.
The Kleene closure L* of L is defined to be .
- ↑ This equation holds because every element of V+ must either be composed from one element of V and finitely many non-empty terms in V or is just an element of V (where V itself is retrieved by taking V concatenated with ε).
- ↑ Droste, M.; Kuich, W. (2009). "Chapter 1: Semirings and Formal Power Series". भारित ऑटोमेटा की पुस्तिका. Monographs in Theoretical Computer Science. Springer. p. 9. doi:10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.
