שאלה 8 במסלול מודלים חישוביים. נתונות שלוש שפות 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}. בסעיף א׳ יש לסווג כל אחת כרגולרית או לא (עם נימוק קצר), ולמצוא מילה לא ריקה בחיתוך L1∩L3. בסעיף ב׳ נתונה מכונת טיורינג חלקית (חסרים 2 מעברים) שבודקת האם מילה בתחילת הסרט שייכת ל-L2, ויש להשלימה כך שתקבל בדיוק את L2.

מכונת טיורינג חלקית עבור L2 (חסרים מעברים) -- p-13.png / p13_diagram2.png (300dpi)

states q0..q7, start q0, accepting q2 (double circle). Edges: q0 --a/X, ימין--> q1; q0 --∆/∆, ימין--> q2(accept); q1 --b/Y, ימין--> q3; q3 --b/Y, ימין--> q4; q4 --a/Z, שמאל--> q6; q6 --(label MISSING)--> q5; q5 --(label MISSING)--> q7. 'ימין'=right, 'שמאל'=left (tape head movement); X,Y,Z are the machine's own marker symbols for a,b,a respectively; ∆ = blank.