תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←השפה המתקבלת על-ידי המכונה M: הגהה |
|||
שורה 11:
<math>L(M)</math>.
<center> <math>L(M) \triangleq L_{acc}= \{ x\mid M(x) = \text{ accept}\}</math></center>
באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה
<math>L_{rej}(M) נדגיש כי לכל קלט ייתכנו שלושה מצבים: המכונה עצרה וקיבלה את הקלט, המכונה עצרה ודחתה את הקלט או המכונה לא עצרה. קלט ש"לא התקבל" על-ידי מכונה הוא קלט שנדחה או שהמכונה לא עצרה בעת החישוב, כלומר
<math>L_\text{not accept} ולכן
<math>L_\text{not accept}= ~L_\text{accept} \bigcap ~L_\text{reject}.</math>
{{-}}
|