פתרון שאלה 7

הרעיון:

נסרוק את הקלט מימין לשמאל, ותוך כדי מעבר נחליף אותיות קטנות באותיות גדולות מתאימות. בסיום מעבר נחזור חזרה ימינה ונחזור שוב על התהליך.

חשוב להקפיד להחליף עבור כל c גם b וגם a, כך נוודא שהמספר שלהם זהה.

הערות:

מכונה מקבלת היא מכונה שקיימים מעברים בטבלת המעברים שמובילים אותנו למצב H. אם אין שרשרת מעברים כזו, המכונה נתקעת ומבחינתנו היא אינה מקבלת את המלה.

מכונה דומה לזו שראינו בשיעור 1, רק שהיא מקבלת, כלומר: עוצרת אם כן, ונתקעת אם לא.