क्लेन स्टार

गणितीय तर्क और कंप्यूटर विज्ञान में, क्लेन स्टार (या क्लेन संचालक या क्लेन क्लोजर) या यूनरी संचालन है, या तो   श्रृंखला (कंप्यूटर विज्ञान) के (गणित) पर या प्रतीकों या वर्णों के समूह पर होता है। । गणित में,इसे सामान्यतौर पर स्वतंत्र एकाभ निर्माण के रूप में जाना जाता है। समूह पर क्लेन स्टार का अनुप्रयोग $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$ बार। वह है,$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.