תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
מ הגהה |
||
שורה 2:
לשם פשטות המודל, על מנת לסמן "קבלה" או "דחייה" נגדיר מצבים סופיים מתאימים <math>q_{acc},q_{rej} \in F</math>. כלומר, על מנת לקבל את הקלט, המכונה צריכה לעבור למצב הסופי <math>q_{acc}</math> ועל מנת לדחותו, על המכונה לעבור למצב <math>q_{rej}</math>, ואין חשיבות לתוכן הסרט בעת מעבר למצב הסופי (כלומר, אינה צריכה לכתוב "0" או "1", המעבר למצב המתאים מספיק).
כמו כן, ניתן להניח ש-<math>q_{acc},q_{rej} </math> הם המצבים הסופיים היחידים, כי מצבים נוספים (למשל <math>q_{acc1}, q_{acc2},...</math>) ניתנים להחלפה באחד משני המצבים לעיל, בהתאם
===השפה המתקבלת על-ידי המכונה M===
| |||