כוכב קלין

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

תכונות:

  1. אם היא קבוצה של מחרוזות, אז  מוגדרת כקבוצה הקטנה ביותר המכילה את  ואת המחרוזת הריקה , וסגורה תחת שרשור.
  2. אם היא קבוצה של תווים, אז  היא קבוצת כל המחרוזות שניתן להרכיב מאוסף של סמלים ב-, כולל המחרוזת הריקה .

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

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

הגדרה וסימוןעריכה

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

  (שפה המורכבת מהמחרוזת הריקה בלבד),
 

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

  לכל  .

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

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

 .

דוגמאותעריכה

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

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

הערות שולייםעריכה

  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 (מהדורה שנייה). New York: Springer. עמ' 656. ISBN 0-387-94258-0. The Kleene closure L* of L is defined to be  .