תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←כריעות למחצה חיובית: M מכריעה שונה מ M מונה רקורסיבית |
|||
שורה 56:
מעט [[w:אטימולוגיה|אטימולוגיה]].
שפה כריעה למחצה חיובית נקראת גם "ניתנת למניה רקורסיבית" מכיוון שלכל שפה כנ"ל קיימת מ״ט E ש"מייצרת" את כל המילים ב־L, כלומר, היא רושמת על סרט הזיכרון עוד ועוד מילים מתוך L, ללא סדר מסויים, כך שכל מילה ב־L תופיע על הסרט אחרי זמן סופי. מכונה כזו נקראת "מונה רקורסיבית" משום שהיא מונה את המילים שב־L.
שפה נקראת "נתנת למניה רקורסיבית" מהסיבה הבאה. נניח ש-<math>L</math> היא שפה נתנת למניה רקורסיבית ע"י מ"ט <math>M</math>. נקח מניה כלשהי של המחרוזות על פני <math>\Sigma^*</math>. כעת נפעיל את <math>M</math> צעד אחד על המחרוזת הראשונה במניה, 2 צעדים על כ"א מ2 המחרוזות הראשונות במניה, 3 צעדים על כ"א מ3 -המחרוזות הראשונות במניה, וכו'. ברור שכל מחרוזת השייכת לL, תזוהה ככזו בשלב כלשהו ע"י כך שM תעצור ותקבל אותה. בכל פעם שמילה מתקבלת, נרשום אותה ברשימה בצד. ▼
▲
נשים לב שהסדר של המניה אינו ידוע. ב[[../תרגילים#שפה כריעה ניתנת למניה לקסיקוגרפית|תרגיל]] נראה שקיימת מ״ט E המונה את L '''לפי סדר לקיסקוגרפי''' אם״ם <math>L\in R</math>.
}}
|