כוכב קלין

בלוגיקה מתמטית ומדעי המחשב, כוכב קלין או סגור קלין ובסימון מתמטי * (Kleene Star, Kleene Closure) היא פעולה אונארית, על קבוצה של מחרוזות או על קבוצה של תווים כלשהם. הפעלה של כוכב קלין על קבוצה ${\displaystyle A}$ מסומנת כ-${\displaystyle A^{*}}$. בכוכב קלין נעשה שימוש נרחב בביטויים רגולריים, והוא ההקשר שבו נטבע ואופיין המונח על ידי סטיבן קלין כדי לייצג אוטומטים מסוימים, אשר בהקשר הזה משמעו "אפס או יותר".

תכונות:

1. אם ${\displaystyle V}$ היא קבוצה של מחרוזות, אז ${\displaystyle V^{*}}$ מוגדרת כקבוצה הקטנה ביותר המכילה את ${\displaystyle V}$ ואת המחרוזת הריקה ${\displaystyle \varepsilon }$, וסגורה תחת שרשור.
2. אם ${\displaystyle V}$ היא קבוצה של תווים, אז ${\displaystyle V^{*}}$ היא קבוצת כל המחרוזות שניתן להרכיב מאוסף של סמלים ב-${\displaystyle V}$, כולל המחרוזת הריקה ${\displaystyle \varepsilon }$.

הקבוצה *V ניתנת לתיאור כקבוצה של מחרוזות סופיות שנוצרו על ידי שרשור שרירותי של אלמנטים של ${\displaystyle V}$, המאפשר את השימוש של אותו תו מספר פעמים בלתי מוגבל.

אם ${\displaystyle V}$ קבוצה ריקה ${\displaystyle \emptyset }$ או היחידון המכיל את המחרוזת הריקה ${\displaystyle \{\varepsilon \}}$, אז ${\displaystyle V^{*}=\{\varepsilon \}}$; אחרת, אם ${\displaystyle V}$ היא קבוצה סופית, אז ${\displaystyle V^{*}}$ הוא קבוצה בת־מנייה.^[1] גם כאשר ${\displaystyle V}$ היא קבוצה בת־מנייה, ${\displaystyle V^{*}}$ הוא קבוצה בת־מנייה.^[2]

הגדרה וסימון

עבור קבוצה נתונה ${\displaystyle V}$ נגדיר:

${\displaystyle V_{0}=\{\varepsilon \}}$ (שפה המורכבת מהמחרוזת הריקה בלבד),

${\displaystyle V_{1}=V}$

ובאופן רקורסיבי נגדיר את האיברים הבאים:

${\displaystyle V_{i+1}=\{wv:w\in V_{i},v\in V\}}$ לכל ${\displaystyle i\geq 0}$.

אם ${\displaystyle V}$ היא שפה פורמלית, אז ${\displaystyle V_{i}}$ היא החזקה ה-${\displaystyle i}$ של הקבוצה ${\displaystyle V}$, קיצור של שירשור של קבוצה ${\displaystyle V}$ עם עצמה ${\displaystyle i}$ פעמים. כלומר, ${\displaystyle V_{i}}$ יכול להיות מובן כקבוצת כל המחרוזות שהן שרשור של ${\displaystyle i}$ איברים של ${\displaystyle V}$, ולעיתים מסמנים אותו ${\displaystyle V^{i}}$.

בכתיב מתמטי, כוכב קלין מוגדר על ידי:^[3]

${\displaystyle V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\{\varepsilon \}\cup V\cup V_{2}\cup V_{3}\cup V_{4}\cup \ldots .}$.

דוגמאות

כוכב קלין על קבוצה בת איבר אחד: ${\displaystyle \{a\}^{*}=\{\varepsilon ,a,aa,aaa,aaaaa,aaaaaa,\dots \}}$.

כוכב קלין על קבוצת מחרוזות: ${\displaystyle \{ab,c\}^{*}=\{\varepsilon ,ab,c,abab,abc,cab,cc,ababab,ababc,abcab\dots \}}$.

הערות שוליים

1. Nayuki Minase (10 במאי 2011). "Countable sets and Kleene star". Project Nayuki. נבדק ב-11 בינואר 2012.
2. Countable sets and Kleene star, Project Nayuki
3. Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Mathematical Logic (2nd ed.). New York: Springer. p. 656. ISBN 0-387-94258-0. The Kleene closure L^* of L is defined to be ${\displaystyle \sideset {}{_{i=0}^{\infty }}\bigcup L^{i}}$.