תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 6:
כמו כן, ניתן להניח ש-<math>q_{acc},q_{rej} </math> הם המצבים הסופיים היחידים, כי מצבים נוספים (למשל <math>q_{acc1}, q_{acc2},...</math>) ניתנים להחלפה באחד משני המצבים לעיל, בהתאם לשאלה האם הם גורמים לקבלה או דחיה.
 
===השפה המתקבלת והנדחית על-ידי המכונה Mמכונה===
 
מכיוון שעל כל קלט, המכונהמכונה <math>M</math> יכולה לענות כן או לא (קבלה או דחיה), היא למעשה מחלקת את מרחב הקלט לשתי קבוצות: קבוצת המילים שעליהן היא עונה "כן" וקבוצת שאר המילים, עליהן היא עונה "לא" או לא עוצרת. נסמן ב-<math>L(M)</math> את קבוצת המילים שהמכונה עונה עליהן "כן" ונקרא לקבוצה זו '''השפה המתקבלת על-ידי המכונה M''',
<math>L(M)</math>.
<center> <math>L(M) \triangleq L_{acc}= \{ x\mid M(x) = \text{ accept}\}</math></center>
באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה <math>L_{rej}(M)=\{ x \mid M(x)=\text{ reject} \}</math>.
 
באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה <math>L_{rej}(M)=\{ x \mid M(x)=\text{ reject} \}</math>. נדגיש כי לכל קלט ייתכנו שלושה מצבים: המכונה עצרה וקיבלה את הקלט, המכונה עצרה ודחתה את הקלט או המכונה לא עצרה. קלט ש"לא התקבל" על-ידי מכונה הוא קלט שנדחה או שהמכונה לא עצרה בעת החישוב., כלומר <math>L_\text{not accept}= \{ x\mid M(x)\ne\text{accept}\}.</math>
 
באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה <math>L_{rej}(M)=\{ x \mid M(x)=\text{ reject} \}</math>. נדגיש כי לכל קלט ייתכנו שלושה מצבים: המכונה עצרה וקיבלה את הקלט, המכונה עצרה ודחתה את הקלט או המכונה לא עצרה. קלט ש"לא התקבל" על-ידי מכונה הוא קלט שנדחה או שהמכונה לא עצרה בעת החישוב. <math>L_\text{not accept}= \{ x\mid M(x)\ne\text{accept}\}</math>
{{-}}
{{חלון מידע|להרחבה בנושא שפות פורמליות, וסימונים מקובלים, ראה [[אוטומטים ושפות פורמליות/שפות פורמליות]].}}