כוכב קלין

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

תכונות:

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

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

אם $V$ קבוצה ריקה $\mathrm{\varnothing }$ או היחידון המכיל את המחרוזת הריקה $\{\epsilon \}$, אז $V^{*}=\{\epsilon \}$; אחרת, אם $V$ היא קבוצה סופית, אז $V^{*}$ הוא קבוצה בת־מנייה. גם כאשר $V$ היא קבוצה בת־מנייה, $V^{*}$ הוא קבוצה בת־מנייה.

הגדרה וסימון

עבור קבוצה נתונה $V$ נגדיר:

$V_0=\{\epsilon \}$ (שפה המורכבת מהמחרוזת הריקה בלבד),

$V_1=V$

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

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

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

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

$V^{*}=\bigcup _{i\in \mathbb{\mathbb{N}}}{V}_i=\{\epsilon \}\cup V\cup V_2\cup V_3\cup V_4\cup \dots .$.

דוגמאות

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

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