בשאלה זו שני סעיפים א-ב. אין קשר בין הסעיפים. ענה על שניהם. לפניך ההגדרה: ריש��ה (prefix) של מילה x היא כל מילה המתקבלת על ידי הורדת מספר כלשהו (אפשר גם 0) של תווים מסוף המילה x, כולל המילה הריקה והמילה x עצמה. לדוגמה: עבור המילה x=abcbad, כל הרישות של x הן: ε,a,ab,abc,abcb,abcba,abcbad. לפניך השפה L מעל הא"ב Σ={a,b,c,d}: L היא אוסף כל המילים שבכל אחת מהרישות שלהן — כולל כל רישה שלמה, כולל המילה הריקה עצמה — מתקיים 0≤#c(w)-#d(w)≤3, כאשר #c(w) מציין את מספר הפעמים ש-c מופיע במילה w, ו-#d(w) מציין את מספר הפעמים ש-d מופיע במילה w. דוגמאות למילים ששייכות ל-L: accbdcacab, bacaabdbcb, abba, cdcdcd, abcbadb. דוגמאות למילים שאינן שייכות ל-L: daac (כי #c(daac)-#d(daac)=-1<0), cddc (כי #c(cddc)-#d(cddc)=-1<0), accbdcacacd (כי #c(w)-#d(w)=4>3).

(a,b)      (a,b)      (a,b)      (a,b)
  ⟲          ⟲          ⟲          ⟲
 q0 --c--> q1 --c--> q2 --c--> q3
 |^ <--d--   |^ <--d--   |^ <--d--
 | d                              | c
 v                                v
 +------------> q4 <--------------+
              (a,b,c,d) ⟲
מצבים מקבלים: q0,q1,q2,q3 (הערך הנוכחי של #c-#d תקין). q4 = מלכודת לא-מקבלת (הערך יצא מהתחום).