نمایش مبدأ برای ستاره کلین

در [[منطق ریاضی]] و [[علوم کامپیوتر]]، '''ستارهٔ کلین''' (یا عملگر کلین یا کلین [[کلوژر]]) یک [[عمل یگانی]] روی مجموعه ای از رشته ها و یا مجموعه ای از سمبل ها یا کاراکتر ها است. در ریاضیات عموما به عنوان ساختار [[مونوئید های ازاد|مونوئید ازاد]] شناخته می شود. اعمال ستاره ی کلین بر روی مجموعه ی <math>{\displaystyle V}
</math> به صورت <math>{\displaystyle V^{*}}</math> نوشته می شود. ستاره ی کلین به طور گسترده برای [[عبارت منظم]] استفاده می شود، که در واقع این زمینه ای بود که در آن توسط [[استیون کول کلینی]] برای تشریح برخی از [[اتوماتای سلولی ساده|اتوماتاها]] معرفی شده بود، که در آن به معنای "صفر یا تعدادی بیشتر تکرار" است.

# اگر <math>{\displaystyle V}</math> مجموعه ای از رشته ها باشد، آنگاه <math>{\displaystyle V^{*}}</math> کوچک ترین [[ابرمجموعه]] از <math>{\displaystyle V}</math> است که شامل رشته ی تهی <math>{\displaystyle \varepsilon }</math> و همچنین تحت عمل [[الحاق (علوم رایانه)]] بسته باشد.
# اگر <math>{\displaystyle V}</math> مجموعه ای از کاراکتر ها یا سمبل ها باشد، آنگاه <math>{\displaystyle V^{*}}</math> مجموعه تمام رشته ها بر روی سمبل های داخل <math>{\displaystyle V}</math> و رشته ی تهی <math>{\displaystyle \varepsilon }</math> است.
مجموعه ی <math>{\displaystyle V^{*}}</math> را می توان به عنوان مجموعه ای که شامل رشته ی تهی و همه رشته های با طول متناهی که توسط الحاق رشته های دلخواه در <math>{\displaystyle V}</math> (که در آن می توان از یک عضو چند بار استفاده کرد) نیز توصیف کرد. اگر <math>{\displaystyle V}</math> مجموعه ی تهی <math>\varnothing</math> و یا مجموعه ی تک عضوی <math>{\displaystyle \{\varepsilon \}}</math> باشد، آنگاه <math>{\displaystyle V^{*}=\{\varepsilon \}}</math> و اگر <math>{\displaystyle V}</math> هر [[مجموعه متناهی]]  یا [[مجموعه شمارا]] نامتناهی دیگر باشد، آنگاه <math>{\displaystyle V^{*}}</math> یک مجموعه ی شمارا نامتناهی خواهد بود. در نتیجه هر [[زبان صوری]] بر روی الفبا <math>{\displaystyle \Sigma }</math> که متناهی یا شمارای متناهی است، شمارا خواهد بود زیرا زیر مجموعه از مجموعه ی شمارا نامتناهی <math>{\displaystyle \Sigma ^{*}}</math> است.

عملگر ها برای [[بازنویسی (ریاضی)]] [[دستور زایشی|دستور های زایشی]] استفاده می شوند.

== تعریف و نمادگذاری ==
اگر مجموعه ی <math>{\displaystyle V}</math> را داشته باشیم، <math>{\displaystyle V^{0}=\{\varepsilon \}}</math> (زبانی که تنها شامل رشته ی تهی است) و <math>{\displaystyle V^{1}=V}</math> تعریف می شوند و همچنین <math>{\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}}</math> برای هر <math>{\displaystyle i>0}</math> به صورت بازگشتی تعریف می شود. اگر <math>{\displaystyle V}</math> یک زبان فرمال باشد، انگاه <math>{\displaystyle V^{i}}</math>، توان iام مجموعه ی <math>{\displaystyle V}</math>، کوتاه شده i بار [[الحاق (علوم رایانه)|الحاق]] مجموعه ی <math>{\displaystyle V}</math> با خودش است. یعنی <math>{\displaystyle V^{i}}</math> در واقع مجموعه ی تمام رشته هایی است که می توانند به صورت الحاق i رشته از <math>{\displaystyle V}</math> نمایش داده شوند. 

تعریف ستاره کلین بر روی <math>{\displaystyle V}</math> به صورت زیر است: 

<math>{\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .}</math> 

این به این معنا است که ستاره ی کلین یک [[عمل یگانی]] [[خودتوانی|خودتوان]] است یعنی <math>{\displaystyle (V^{*})^{*}=V^{*}}</math> برای هر مجموعه دلخواه <math>{\displaystyle V}</math> از رشته ها یا کاراکتر ها، به طوری که <math>{\displaystyle (V^{*})^{i}=V^{*}}</math> به ازای هر <math>{\displaystyle i\geq 1}</math>. 

== مثبت کلین ==
در برخی از مطالعات [[زبان صوری|زبان های صوری]] (به عنوان مثال تئوری خانواده زبان های انتزاعی) نوعی متفاوت از عملیات ستاره کلین، به نام مثبت کلین استفاده می شود. مثبت کلین عبارت <math>{\displaystyle V^{0}}</math> را از اجتماعی که در بالل آمده بود حذف می کند، به عبارت دیگر مثبت کلین بر روی مجموعه ی <math>{\displaystyle V}</math> به صورت زیر است:

<math>{\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots .}</math>  

یا 

.<math>{\displaystyle V^{+}=V^{*}V}</math>

== مثال‌ها ==
مثالی از اعمال ستاره ی کلین بر روی مجموعه ای از رشته ها:

<span lang="fa" dir="ltr">{"ab","c"}<sup>*</sup> = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.</span>

مثالی از اعمال مثبت کلین بر روی مجموعه ای از کاراکتر ها:

<span lang="fa" dir="ltr">{"a", "b", "c"}<sup>+</sup> = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.</span>

اعمال ستاره ی کلین بر همان مجموعه از کاراکتر ها:

<span lang="fa" dir="ltr">{"a", "b", "c"}<sup>*</sup> = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.</span>

اعمال ستاره ی کلین بر روی مجموعه ی تهی:

<span lang="fa" dir="ltr">∅<sup>*</sup> = {ε}.</span>

اعمال مثبت کلین بر روی مجموعه ی تهی:

<span lang="fa" dir="ltr">∅<sup>+</sup> = ∅ ∅<sup>*</sup> = { } = ∅</span>

که در آن الحاق  [[خاصیت شرکت‌پذیری|شرکت‌پذیر]] و اما دارای [[خاصیت جابه‌جایی]] نیست.

اعمال ستاره ی کلین و مثبت کلین بر روی مجموعه ی تک عضوی شامل رشته ی تهی:

اگر <math>{\displaystyle V=\{\varepsilon \}}</math> باشد، آنگاه <math>{\displaystyle V^{i}=\{\varepsilon \}}</math> برای هر i، بنابراین <math>{\displaystyle V^{*}=V^{+}=\{\varepsilon \}}</math>.

== تعمیم ==
رشته هایی از یک [[مونوئید]] و الحاق به عنوان [[عملگر دوتایی]] و ε به عنوان عضو همانی. ستاره ی کلین نه تنها برای رشته ها بلکه برای هر مونوئیدی تعریف می شود.

به طور دقیق تر،اگر <span lang="fa" dir="ltr">(''M'', ⋅)</span> یک مونوئید و ''S'' ⊆ ''M،'' آنگاه <sup>*</sup>''S'' کوچک ترین زیرمونوئیدی از M است که شامل S می باشد. به عبارت دیگر، <sup>*</sup>''S'' شامل عضو خنثی M، مجموعه ی S، به طوری که اگر<sup>*</sup> ''x'',''y'' ∈ ''S ،'' آنگاه <sup>*</sup>''x''⋅''y'' ∈ ''S''.

== جستارهای وابسته ==
* [[عمل الحاق (علوم کامپیوتر)|الحاق]]
* [[جبر کلین]]

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* Sudkamp, T. A. , ''An Introduction to the Theory of Computer Science, Languages and Machines'', 3rd ed. , Pearson Education, Inc. , 2006. {{ISBN|0-321-32221-5|en}} [http://www.amazon.com/Languages-Machines-Introduction-Computer-Science/dp/0321322215]
{{پایان چپ‌چین}}

[[رده:پردازش زبان‌های طبیعی]]
[[رده:دستور زبان]]
[[رده:زبان‌های صوری]]
[[رده:نظریه محاسبات]]