נתונה השפה L1 מעל האלפ"ב {a,b,c}: L1 = {c^(1+k+n) b^k a^(2n) | n,k≥1}. בסעיף ב נתונה השפה L2 = L1 · d · R(L1) מעל האלפ"ב {a,b,c,d} (כאשר R(L) היא שפת המילים ההפוכות של מילות L).

מהי המילה הקצרה ביותר בשפה L1?

בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L1.

נגדיר את השפה L2 = L1 · d · R(L1) מעל האלפ"ב {a,b,c,d}. בעבור כל אחת מן המילים שלהלן, ציינו אם היא שייכת לשפה L2 ונמקו (אין צורך לבנות אוטומט בעבור השפה L2): cccbaaddaabccc, cccbaadccbaa, cccbaadaaaabcccc.