כוכב קלין

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

תכונות:

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

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

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

הגדרה וסימון

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

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

$V_{1}=V$

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

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

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

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

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

דוגמאות

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

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