ستاره کلین

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

اگر ${\displaystyle V}$ مجموعه ای از رشته ها باشد، آنگاه ${\displaystyle V^{*}}$ کوچک ترین ابرمجموعه از ${\displaystyle V}$ است که شامل رشته ی تهی ${\displaystyle \varepsilon }$ و همچنین تحت عمل الحاق (علوم رایانه) بسته باشد.
اگر ${\displaystyle V}$ مجموعه ای از کاراکتر ها یا سمبل ها باشد، آنگاه ${\displaystyle V^{*}}$ مجموعه تمام رشته ها بر روی سمبل های داخل ${\displaystyle V}$ و رشته ی تهی ${\displaystyle \varepsilon }$ است.

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

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

تعریف و نمادگذاری

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

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

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

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

مثبت کلین

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

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

یا

. ${\displaystyle V^{+}=V^{*}V}$

مثال ها

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

{"ab","c"}^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

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

{"a", "b", "c"}⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

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

{"a", "b", "c"}^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

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

∅^* = {ε}.

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

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

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

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

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

تعمیم

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

به طور دقیق تر،اگر (M, ⋅) یک مونوئید و S ⊆ M، آنگاه ^*S کوچک ترین زیرمونوئیدی از M است که شامل S می باشد. به عبارت دیگر، ^*S شامل عضو خنثی M، مجموعه ی S، به طوری که اگر^* x,y ∈ S ، آنگاه ^*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 [۱]