שאלה זו עוסקת בפעולות בין שפות (סעיף א) ובבניית אוטומט מחסנית לשפה מעל {a,b,c} (סעיף ב).

לפניכם שש שפות מעל האלפבית {0,1}: L1=∅, L2=Σ*, L3={ε}, L4={0110}, L5={ε,110,00,001}, L6={1,0110,110,01}. כתבו את השפה המתקבלת מכל אחת מחמש הפעולות שלהלן: (1) L5∩L6 (2) L2^R (3) L1L6 (4) L3L4 (5) L4*L5.

נתונה השפה L מעל {a,b,c}: L={(ab)^k c^m b^(m+3k) | k,m>=0}. בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L.