כוכב קלין

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

תכונות:

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

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

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

הגדרה וסימון

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

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

V₁ = V

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

{V_i+1 = { wv : w ∈ Vi , v ∈ V , לכל i>0.

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

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

$V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\{\varepsilon \}\cup V\cup V_{2}\cup V_{3}\cup V_{4}\cup \ldots .$

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22480356כוכב קלין