פתיחת התפריט הראשי

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

תכונות:

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

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

אם קבוצה ריקה ∅ או קבוצה בעלת האלמנט הבודד {ε} שהוא המילה הריקה, אז {V* = {ε; אחרת, אם V היא קבוצה סופית, אז *הוא קבוצה בת מנייה.[1] גם כאשר V היא קבוצה בת מנייה, *V הוא קבוצה בת מנייה.[2]

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

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

{V0 = {ε (שפה המורכבת מהמחרוזת הריקה בלבד),
V1 = V

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

{Vi+1 = { wv : wVi , vV , לכל i>0.

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

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

 

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

כוכב קלין על קבוצה בת איבר אחד: {...,"ε, "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa}‏ = *{"a"}

כוכב קלין על קבוצת מחרוזות: {...,"ε, "ab", "c", "abab", "cab", "abc", "cc", "ababc", "abcab}‏ = *{"ab","c"}

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

  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  .