מודל חישובי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
Shalomori123 (שיחה | תרומות) ←אוטומט סופי: תיקנתי דקדוק תגית: עריכה מיישום נייד |
||
שורה 14:
*: <math>\delta : Q \times E \rightarrow Q</math>. למעשה, <math>\delta</math> מקבלת מצב ואות קלט, ומחזירה את המצב הבא.
* <math>F</math> היא קבוצת המצבים המקבלים באוטומט.
האוטומט מקבל מילת קלט <math>w \isin \Sigma^*</math> (נוכל גם לומר כי <math>w=w_0w_1...w_{n-1}, \forall i<n: w_i \isin \Sigma</math>), וקורא את האותיות בה בזו אחר זו. הוא מתחיל את ריצתו על המילה במצב <math>q_0</math>, משם עובר למצב <math>q_1=\delta (q_0,w_0)</math>, וכך הלאה (באמצעות הכלל <math>q_i= \delta(q_{i-1},w_{i-1})</math>. נאמר כי המילה שייכת לשפת האוטומט, [[אם"ם]] הריצה של האוטומט על המילה מסתיימת במצב מקבל, כלומר, <math>q_{|w|} \isin F</math>.
קיימים שני סוגים של אוטומט סופי: [[אוטומט סופי דטרמיניסטי]] ו[[אוטומט סופי לא דטרמיניסטי]]. משפט הדטרמיניזציה קובע כי שני המודלים הללו שקולים מבחינת יכולת החישוב שלהם, כלומר לכל אוטומט סופי לא דטרמיניסטי <math>N</math> קיים אוטומט סופי דטרמיניסטי <math>A</math> כך שמתקיים <math>L(A)=L(N)</math>.
|