שאלה זו, א-ב, אין קשר בין הסעיפים. ענה על שניהם.

נתון הא"ב Σ={a,b}. בנה אוטומט מחסנית המקבל בעבור השפה L={a²b^k a^n | n>0, k>0, n<k}.

(אין קשר לסעיף א.) בנה מכונת טיורינג המקבלת כקלט מספר x בייצוג אונרי, ומחשבת את ערכה של הפונקציה שלפניך: f(x)=x+1 אם x<2; f(x)=x-1 אם x≥2.