בשאלה זו שני סעיפים, א-ב, שאין ביניהם קשר. בסעיף א שתי טענות נכון/לא נכון על שפות מעל {a,b}; בסעיף ב שפה L מעל {a,b,c} שמוגדרת בתנאי זוגיות ותנאי על תת-מחרוזות אסורות, ובה בודקים שייכות מילים ובונים אוטומט סופי דטרמיניסטי (שאינו בהכרח מלא) המקבל אותה.

לפניכם שתי טענות (1)–(2) בנוגע לשפות L1, L2 שמעל הא"ב {a, b}. בעבור כל טענה, ציינו אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא לא נכונה – הביאו דוגמה נגדית. אין קשר בין הטענות. (1) אם L1, L2 הן שפות לא רגולריות, בהכרח L1 ∩ L2 היא שפה לא רגולרית.

(2) (L1 · L2)^n תמיד שווה ל-L1^n · L2^n.

נתונה השפה L מעל הא"ב {a, b, c}: L = { w | #a(w) + #c(w) הוא מספר זוגי, והרצפים ab, bc אינם מופיעים ב-w } #a(w) מציין את מספר המופעים של a במילה w. #c(w) מציין את מספר המופעים של c במילה w. דוגמה למילה בשפה L היא cba, כי סכום המופעים של האות a (1) והאות c (1) הוא מספר זוגי (2), והרצפים ab ו-bc אינם מופיעים במילה. (1) לפניכם חמש מילים. בנוגע לכל אחת מהן ציינו אם המילה שייכת לשפה L או לא. נמקו את תשובתכם. aaccc, aab, ε, baa, cbbba

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