בשאלה זו שני סעיפים, א-ב, שאין ביניהם קשר. בסעיף א מחשבים ישירות חמש פעולות (חיתוך, הפכית, שרשור) על שש שפות נתונות מעל {0,1}; בסעיף ב בונים אוטומט מחסנית דטרמיניסטי לשפה L = {(ab)^k c^m b^(m+3k) | k,m≥0} מעל {a,b,c}.

לפניכם שש שפות מעל הא"ב {0, 1}: Σ* – מציין את שפת כל המילים מעל הא"ב {0, 1}. L1 = ∅ L2 = Σ* L3 = {ε} L4 = {0110} L5 = {ε, 110, 00, 001} L6 = {1, 0110, 110, 01} כתבו את השפה המתקבלת מכל אחת מחמש הפעולות שלהלן: (1) L5 ∩ L6 (2) L2^R (3) L1 · L6 (4) L3 · L4 (5) L4 · L5

נתונה השפה L מעל הא"ב {a, b, c}: L = { (ab)^k c^m b^(m+3k) | k, m ≥ 0 } בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L.