क्लेन स्टार

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

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

सेट$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.