נתונה השפה L1 מעל הא"ב {a, b, c}, המורכבת מרצפים מן הצורה a^n b^k c^n, כך ש-n הוא מספר אי־זוגי ושארית החלוקה של k ב-3 היא 1. בין כל שני רצפים מפרידה האות b.
דוגמאות למילים ששייכות ל-L1: abc, abbbbcbaaabccc.
דוגמאות למילים שאינן שייכות ל-L1: abbc (שארית החלוקה של k=2 ב-3 אינה 1), abcabc (האות b אינה מפרידה בין הרצפים), abccc (מספר ה-a אינו שווה למספר ה-c), aabcc (מספר ה-a זוגי).
בנו אוטומט מחסנית עבור השפה L1.
נתונה השפה L2 מעל הא"ב {a, b, c}:
L2 = { a^k b^m c^x | 0 ≤ k < 5, 0 ≤ m < 5, 0 ≤ x }
נגדיר L3 = L2 ∩ L1. כתבו את כל המילים שבשפה L3.
נתונה השפה L1 מעל הא"ב {a, b, c}, המורכבת מרצפים מן הצורה a^n b^k c^n, כך ש-n הוא מספר אי־זוגי ושארית החלוקה של k ב-3 היא 1. בין כל שני רצפים מפרידה האות b.
דוגמאות למילים ששייכות ל-L1: abc, abbbbcbaaabccc.
דוגמאות למילים שאינן שייכות ל-L1: abbc (שארית החלוקה של k=2 ב-3 אינה 1), abcabc (האות b אינה מפרידה בין הרצפים), abccc (מספר ה-a אינו שווה למספר ה-c), aabcc (מספר ה-a זוגי).
בנו אוטומט מחסנית עבור השפה L1.
נתונה השפה L2 מעל הא"ב {a, b, c}:
L2 = { a^k b^m c^x | 0 ≤ k < 5, 0 ≤ m < 5, 0 ≤ x }
נגדיר L3 = L2 ∩ L1. כתבו את כל המילים שבשפה L3.