חבורה למחצה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 54:
== חבורות למחצה ואוטומטים ==
[[אוטומט סופי|אוטומט]] הוא מנגנון בסיסי במדעי המחשב התאורטיים, המתואר בדרך כלל כ[[גרף מכוון]] עם מידע נוסף על הקשתות, כגון אותיות הקלט והפלט של האוטומט. אפשר לתאר [[אוטומט דטרמיניסטי]] עם מרחב מצבים 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>.
| |||