כוכב קלין

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

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

תכונות:

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

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

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

הגדרה וסימון[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Nayuki Minase (10 במאי 2011). "Countable sets and Kleene star". Project Nayuki. בדיקה אחרונה ב-11 בינואר 2012. 
  2. ^ 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 .