נתונות שלוש שפות L1,L2,L3 מעל {a,b}: L1={w·R(w) | w∈{a^n b^m | n=m%2, m≥0}}, L2={a^n b^(2n) a^n | n≥0}, L3={(ab)^n(ba)^m | n≥m, m≥0}.
מכונת טיורינג חלקית עבור L2 (חסרים מעברים)
מצבים q0–q7, מצב התחלתי q0, מצב מקבל q2 (עיגול כפול). המעברים שבשרטוט:
q0 --a/X, ימין--> q1
q0 --∆/∆, ימין--> q2 (מקבל)
q1 --b/Y, ימין--> q3
q3 --b/Y, ימין--> q4
q4 --a/Z, שמאל--> q6
q6 --(ללא סימון)--> q5
q5 --(ללא סימון)--> q7
סעיף א(1)-(2)
(1) כתבו לגבי כל שפה (L1, L2, L3) האם היא רגולרית או לא, ונמקו בקצרה. (2) כתבו מילה שאינה ריקה השייכת לשפת החיתוך L1 ∩ L3.
סעיף ב
לפניכם מכונת טיורינג חלקית שבודקת האם מילה בתחילת הסרט שייכת לשפה L2 (הנתונה לעיל). המכונה כוללת את כל המצבים הנדרשים (כולל סימון מצב מקבל). העתיקו למחברת הבחינה את המכונה החלקית הנתונה והשלימו אותה כך שתקבל את השפה L2. הערות: אין צורך לשמור את מילת הקלט על הסרט; אין להוסיף מצבים; ניתן להוסיף מעברים.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.