(1) לפניכם שלוש שפות L₁–L₃ מעל הא״ב {a, b, c}:

בנוגע לכל אחת מן השפות L₁–L₃, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).

(2) לפניכם שלוש שפות L₄–L₆ מעל הא״ב {a, b, c}:

בנוגע לכל אחת מן השפות L₄–L₆, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).

לפניכם השפה L מעל הא״ב {a, b, c}:

w היא מילה מעל הא״ב {b, c} המאופיינת באופן שלהלן:

• אם n + k מתחלק ב־3 בלי שארית, w היא מילה ריקה.
• אם n + k מתחלק ב־3 עם שארית 1, w היא מילה שאינה מכילה את האות b כלל.
• אם n + k מתחלק ב־3 עם שארית 2, w היא מילה שאינה מכילה את האות c כלל.

✎ דוגמה למילה השייכת לשפה L

a bb aaa ccc — כאשר aⁿ הוא a, b^m הוא bb, a^k הוא aaa ו־w הוא ccc.

הסבר: n = 1, k = 3. n + k מתחלק ב־3 עם שארית 1, ו־w היא מילה שאינה מכילה את האות b.

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