לפניכם שני סעיפים, א–ב, שאינם קשורים זה לזה. עליכם לענות על שניהם.

לפניכם השפות הרגולריות L1 ו-L2 מעל הא"ב {a,b}: L1={a^(2k) | k>=0}, L2={b^(2k+1) | k>=0}. הוכיחו בעזרת תכונות הסגירות של השפות הרגולריות שהשפה L3 רגולרית: L3={a^n b^m | n,m>=0, m%2 != n%2}.

נתונות השפות הבאות: L = {a^z w1 w2 ... wk d^(k+1) | z%2=1, wi∈L1, k>0}, L1={b^n c^m | n,m>0}. דוגמה למילה בשפה aaabbcbccddd: a^z=aaa, w1=bbc, wk=bcc, d^(k+1)=ddd (מספר תווי a הוא אי-זוגי; k=2 מילים מ-L1 בין ה-a-ים ל-d-ים, לכן d^(k+1)=d^3). (1) כתבו את המילה הקצרה ביותר בשפה L. (2) נתון אוטומט מחסנית דטרמיניסטי חלקי המקבל את השפה L. האוטומט כולל את כל המצבים (כולל סימון מצב מקבל). עליכם להשלים את המעברים החסרים ואת פירוט המעברים הקיימים (התו במעבר, הסימן בראש המחסנית והפעולה על המחסנית). הערה: אין להוסיף או להוריד מצבים מהאוטומט. העתיקו את אוטומט המחסנית למחברת הבחינה והשלימו אותו כך שיקבל את השפה L.