כוכב קלין

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

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

אם  קבוצה ריקה  או היחידון המכיל את המחרוזת הריקה , אז ; אחרת, אם  היא קבוצה סופית, אז  הוא קבוצה בת־מנייה. גם כאשר  היא קבוצה בת־מנייה,  הוא קבוצה בת־מנייה.

 הגדרה וסימון 
עבור קבוצה נתונה  נגדיר:
  (שפה המורכבת מהמחרוזת הריקה בלבד),

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

 לכל .

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

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

דוגמאות
כוכב קלין על קבוצה בת איבר אחד: .

כוכב קלין על קבוצת מחרוזות: .

 הערות שוליים 

קטגוריה:שפות פורמליות
קטגוריה:דקדוק
קטגוריה:סימני כתב