חבורה למחצה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 51:
תת-קבוצה לא ריקה של חבורה למחצה S היא '''אידיאל''' אם היא סגורה לכפל מימין ומשמאל באברי S. למשל, אם ב-S יש איבר אפס 0, אז {0} הוא אידיאל. חבורה למחצה היא '''פשוטה''' אם אין לה אידיאלים למעט עצמה.
כל חבורה למחצה אפשר לשכן בחבורה פשוטה. את החבורה למחצה {0,1} (עם הכפל הרגיל) אי אפשר לשכן בחבורה למחצה פשוטה סופית. חבורה למחצה פשוטה היא '''פשוטה לחלוטין''' אם יש לה אידמפוטנט פרימיטיבי (לדוגמה, אם היא סופית). '''משפט ריס''' (Rees, 1940) מתאר את החבורות למחצה שהן פשוטות לחלוטין בתור אלו שמתקבלות מבניה מטריציאלית מסוימת ("Rees matrix semigroup" מעל חבורה).
== חבורות למחצה ואוטומטים ==
[[אוטומט]] הוא מנגנון בסיסי במדעי המחשב התאורטיים, המתואר בדרך כלל כ[[גרף מכוון]] עם מידע נוסף על הקשתות, כגון אותיות הקלט והפלט של האוטומט. אפשר לתאר אוטומט עם מרחב מצבים Q ואלפבית <math>\ \Sigma</math> גם כצמד פעולות: של המונויד <math>\ \Sigma^*</math> (אוסף המלים הסופיות, עם פעולת ההדבקה) על Q, ושל Q על <math>\ \Sigma^*</math>, באופן הבא.
* מגדירים פעולה חלקית של <math>\ \Sigma</math> על Q לפי <math>\ q \cdot a = p</math> כאשר האות a מעבירה מן המצב q למצב p. הפעולה מוגדרת באופן חד-ערכי כאשר האוטומט '''דטרמיניסטי''' (היינו יש לכל היותר חץ אחד מ-q שהקלט שלו הוא a), והיא שלמה כאשר האוטומט '''שלם''' (יש לכל הפחות חץ אחד מ-q שהקלט שלו הוא a).
* פעולה זו מומשכת לפעולה (ימנית) של <math>\ \Sigma^*</math> על-ידי <math>\ q \cdot (a w) = (q\cdot a) \cdot w \</math>.
* בדומה לזה מגדירים פעולה חלקית של Q על <math>\ \Sigma</math> לפי <math>\ q \circ a = b</math> כאשר המעבר מן המצב q עם הקלט a מחזיר את הקלט b. גם פעולה זו מוגדרת באופן חד-ערכי כאשר האוטומט דטרמיניסטי, והיא שלמה כאשר האוטומט שלם.
* פעולת Q מורחבת לפעולה <math>\ \Sigma^*</math> לפי <math>\ q \circ (aw) = (q \circ a)[(q\cdot a) \circ w]</math>.
==קישורים חיצוניים==
| |||