בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

נתונות שלוש שפות L1 , L2 , L3 מעל הא"ב {a, b, c} . לפניכם שלוש טענות. בנוגע לכל אחת מן הטענות, קבעו אם היא נכונה או לא נכונה. אם היא נכונה – הסבירו מדוע, ואם היא לא נכונה – הפריכו אותה באמצעות דוגמה נגדית: בחרו שפות ספציפיות והראו שעבורן הטענה לא מתקיימת.

R(R(L1) · R(L2)) = L1 · L2

L1 · (L2 ∪ L3) = (L1 · L2) ∪ (L1 · L3)

L1 ∩ (L2 · L3) = (L1 ∩ L2) · (L1 ∩ L3)

נתונה השפה L מעל הא"ב {a, b, c} : L = {aⁱ bʲ cⁱ⁻ʲ | i ≥ 4, (i − j) ≥ 3} בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L .