כוכב קלין

מתוך ויקיפדיה, האנציקלופדיה החופשית

בלוגיקה מתמטית ומדעי המחשב, כוכב קלין או סגור קלין ובסימון מתמטי * (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 .