אוטומטים ושפות פורמליות/אוטומט סופי דטרמיניסטי: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מבוא לאוטומטים סופיים. |
←מה מגדיר מכונת מצבים: הגדרה אינטואיטיבית |
||
שורה 7:
== מה מגדיר מכונת מצבים ==
נביט במכונה שבדוגמא. מה נדרש כדי להגדיר את כלל האלמנטים של המכונה בצורה מפורשת מדוייקת וחד-חד-ערכית?
* '''קבוצת מצבים''' - הקבוצה שמכילה את כל המצבים האפשריים של המכונה. מסומנת לרוב ב-<math>Q</math>.
* '''אלפבית''' - קבוצת האותיות שהמכונה מכירה. מסומנת לרוב ב-<math>\Sigma</math>
* '''מצב התחלתי''' - המצב שבו מתחילה המכונה. מסומן כ-<math>q_0</math>
* '''מצבים מקבלים''' - קבוצת המצבים שביום עיבוד הקלט בהם מסמל "קבלה" של הקלט. נקראים גם מצבים סופיים, ומסומנים ב<math>F</math>. נשים לב שזוהי תת-קבוצה של כלל מצבי המכונה, כלומר <math>F\subseteq Q</math>
בדוגמא לעיל:
* <math>Q=\{p,q\}</math>
* <math>\Sigma=\{a\}</math>
* <math>q_0=p</math>
* <math>F=\{q\}</math>
האם כלל האלמנטים מוגדרים כעת? מה עדיין חסר? {{ש}}
- ''' ה"חיצים"''', מעברי המכונה לכל קלט וקלט. כיצד ניתן להגדיר את המעברים הללו בצורה מתמטית?
| |||