क्लेन स्टार

गणितीय तर्क और कंप्यूटर विज्ञान में, क्लेन स्टार (या क्लेन संचालक या क्लेन क्लोजर) या यूनरी संचालन है, या तो श्रृंखला (कंप्यूटर विज्ञान) के गणित) पर या प्रतीकों या वर्णों के समूह पर होता है। गणित में,इसे सामान्यतौर पर स्वतंत्र एकाभ निर्माण के रूप में जाना जाता है। समूह पर क्लेन स्टार का अनुप्रयोग $V$ के रूप में $V^{*}$ लिखा गया है| यह नियमित अभिव्यक्तियों के लिए व्यापक रूप से उपयोग किया जाता है, जो संदर्भ है जिसमें स्टीफन क्लेन द्वारा इसे कुछ ऑटोमेटा सिद्धांत की विशेषता के लिए प्रस्तुत किया गया था, जहां इसका अर्थ शून्य या अत्यधिक पुनरावृति है।

1. यदि $V$ श्रंखला का समुच्चय है, फिर $V^{*}$के सबसे छोटे अधिसमुच्चय के रूप में परिभाषित किया गया है $V$ जिसमें रिक्त श्रृंखला है $\varepsilon$ और संयोजन के अंतर्गत समापन (गणित) है।
2. यदि $V$ प्रतीकों या वर्णों का समूह है, तो रिक्त श्रंखला सहित $\varepsilon$, $V^{*}$में प्रतीकों पर $V$ सभी श्रृंखला का समुच्चय है |

समूह $V^{*}$ रिक्त श्रंखला और सभी परिमित-लंबाई वाले श्रंखला के समूह के रूप में भी वर्णित किया जा सकता है, जो अपने ढंग से $V$ तत्वों को जोड़कर उत्पन्न किया जा सकता है, एक ही तत्व को कई बार उपयोग करने की अनुमति देता है। यदि $V$ या तो रिक्त श्रंखला ∅ या एकल समुच्चय $\{\varepsilon \}$ है, तब $V^{*}=\{\varepsilon \}$ है; यदि $V$ तब कोई अन्य परिमित समुच्चय या गणनीय रूप से अपरिमित समुच्चय $V^{*}$ है, गणनीय अपरिमित समुच्चय है। परिणामस्वरूप, प्रत्येक औपचारिक भाषा एक परिमित या गणनीय रूप से अनंत वर्णमाला पर $\Sigma$ गणनीय है, क्योंकि यह गणनीय अपरिमित समुच्चय का उपसमुच्चय $\Sigma ^{*}$ है |

संचालकों का उपयोग प्रजनक व्याकरण के पुनर्लेखन नियमों में किया जाता है।

परिभाषा और संकेतन

दिए गए समूह $V$ को परिभाषित करना है।

$V^{0}=\{\varepsilon \}$ (सिर्फ रिक्त श्रृंखला वाली भाषा),

$V^{1}=V$

और पुनरावर्ती रूप से समुच्चय को परिभाषित करें

$V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}$ प्रत्येक के लिए $i>0$.

यदि $V$ एक औपचारिक भाषा है, तो $V^{i}$, $i$-समुच्चय $V$ की शक्ति, संयोजन के लिए एक कड़ी है | वह, $V^{i}$सभी श्रंखला (कंप्यूटर साइंस) के समुच्चय के रूप में समझा जा सकता है जिसे $i$ में श्रंखला $V$ के संयोजन के रूप में दर्शाया जा सकता है |

$V$ पर क्लेन स्टार की परिभाषा है |

$V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .$

इसका अर्थ यह है कि क्लेन स्टार संचालक एक वर्गसम यूनरी ऑपरेटर है: $(V^{*})^{*}=V^{*}$ किसी भी समूह $V$ के लिए श्रृंखला या वर्णों की, जैसा $(V^{*})^{i}=V^{*}$ सभी $i\geq 1$ के लिए है।

क्लीन प्लस

कुछ औपचारिक भाषा अध्ययनों में, (उदाहरण के लिए भाषाओं का सार समूह) क्लेन स्टार संचालन पर भिन्नता जिसे क्लेन प्लस कहा जाता है, का उपयोग किया जाता है। उपरोक्त समूह में क्लेन प्लस $V^{0}$ छोड़ देता है | दूसरे शब्दों में, क्लेन प्लस $V$ है

$V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots .$

या

$V^{+}=V^{*}V$

उदाहरण

श्रंखला के समूह पर क्रियान्वित क्लेन स्टार का उदाहरण:

{एबी, सी}^* = { ε, एबी, सी, एबीबी, एबीसी, कैब, सीसी, अबाबाब, एबीबीसी, एबीसीबी, एबीसीसी, कैबाब, कैबब, सीसीएबी, सीसीसी, ...}।

क्लेन प्लस का उदाहरण वर्णों के सेट पर लागू होता है:

{ए, बी, सी}⁺ = {ए, बी, सी, एए, एबी, एसी, बीए, बीबी, बीसी, सीए, सीबी, सीसी, एएए, एएबी, ...}।

क्लेन स्टार समान वर्ण सेट पर लागू होता है:

{ए, बी, सी}^* = { ε, ए, बी, सी, एए, एबी, एसी, बीए, बीबी, बीसी, सीए, सीबी, सीसी, आआ, एएबी, ...}।

खाली सेट पर लागू क्लेन स्टार का उदाहरण:

∅^{*</सुप> = {ε}.}

खाली सेट पर लागू क्लेन प्लस का उदाहरण:

∅⁺ = ∅ ∅^* = { } = ∅,

जहां संयोजन एक साहचर्य और गैर-अनुवर्ती उत्पाद है।

खाली स्ट्रिंग वाले सिंगलटन सेट पर लागू क्लेन प्लस और क्लेन स्टार का उदाहरण:

अगर $V=\{\varepsilon \}$, तब भी $V^{i}=\{\varepsilon \}$ प्रत्येक के लिए $i$, इस तरह $V^{*}=V^{+}=\{\varepsilon \}$.

सामान्यीकरण

स्ट्रिंग्स बाइनरी ऑपरेशन के रूप में संयोजन के साथ एक मोनोइड बनाते हैं और ε पहचान तत्व। क्लेन स्टार को किसी भी मोनोइड के लिए परिभाषित किया गया है, न कि केवल स्ट्रिंग्स के लिए। अधिक सटीक रूप से, (M, ⋅) को एक मोनोइड होने दें, और S ⊆ M. फिर S^* M युक्त S का सबसे छोटा उपमोनाइड है; यानी एस^* में M, समुच्चय S का तटस्थ तत्व शामिल है, और ऐसा है कि यदि x,y ∈ S^*, तो x⋅y ∈ S^{*</सुप>.}

इसके अलावा, क्लेन स्टार को बीजगणितीय संरचना में *-ऑपरेशन (और संघ) को शामिल करके पूर्ण स्टार सेमिरिंग की धारणा से सामान्यीकृत किया जाता है।

यह भी देखें

• वाइल्डकार्ड चरित्र
• ग्लोब (प्रोग्रामिंग)

अग्रिम पठन

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley.