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