כוכב קלין
בלוגיקה מתמטית ומדעי המחשב, כוכב קלין או סגור קלין ובסימון מתמטי * (Kleene Star, Kleene Closure) היא פעולה אונארית, על קבוצה של מחרוזות או על קבוצה של תווים כלשהם. הפעלה של כוכב קלין על קבוצה A מסומנת כ *A. בכוכב קלין נעשה שימוש נרחב בביטויים רגולריים, והוא ההקשר שבו נטבע ואופיין המונח על ידי סטיבן קלין כדי לייצג אוטומטים מסוימים, אשר בהקשר הזה משמעו "אפס או יותר".
תכונות:
- אם V היא קבוצה של מחרוזות, אז *V מוגדרת כקבוצה הקטנה ביותר המכילה את V ואת המחרוזת הריקה ε, וסגורה תחת שרשור.
- אם V היא קבוצה של תווים, אז *V היא קבוצת כל המחרוזות שניתן להרכיב מאוסף של סמלים ב-V, כולל המחרוזת הריקה ε.
הקבוצה *V ניתנת לתיאור כקבוצה של מחרוזות סופיות שנוצרו על ידי שרשור שרירותי של אלמנטים של V, המאפשר את השימוש של אותו תו מספר פעמים בלתי מוגבל.
אם V קבוצה ריקה ∅ או קבוצה בעלת האלמנט הבודד {ε} שהוא המילה הריקה, אז {V* = {ε; אחרת, אם V היא קבוצה סופית, אז *V הוא קבוצה בת מנייה.[1]
הגדרה וסימון
עבור קבוצה נתונה V נגדיר:
- {V0 = {ε (שפה המורכבת מהמחרוזת הריקה בלבד),
- V1 = V
ובאופן רקורסיבי נגדיר את האיברים הבאים:
- {Vi+1 = { wv : w ∈ Vi , v ∈ V , לכל i>0.
אם V היא שפה פורמלית, אז Vi, היא החזקה ה-i של הקבוצה V, קיצור של שירשור של קבוצה V עם עצמה i פעמים. כלומר, Vi יכול להיות מובן כקבוצת כל המחרוזות שהן שרשור של i איברים של V.
בכתיב מתמטי, כוכב קלין מוגדר על ידי:[2]
הערות שוליים
- ^ Nayuki Minase (10 במאי 2011). "Countable sets and Kleene star". Project Nayuki. נבדק ב-11 בינואר 2012.
{{cite web}}: (עזרה) - ^ Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994). Mathematical Logic (2nd ed.). New York: Springer. p. 656. ISBN 0-387-94258-0.
The Kleene closure L* of L is defined to be .
