נתונה השפה L מעל הא"ב {a, b, c}:

L = { a^n b^m c^k | אם n%2 = 0 : m%2 = 0 , n = m/2 + k , n, m, k > 0 אם n%2 = 1 : n ≤ m + k - 2 }

דוגמה למילה בשפה בעבור n זוגי: a a a a b b c c c (n=4, m=2, k=3). הסבר: n%2 = 0, ובהתאם גם m%2 = 0, ומתקיים 4 = 3 + (2/2), וגם n, m, k > 0.

דוגמה למילה בשפה בעבור n אי-זוגי: a a a b b b c c c c (n=3, m=3, k=4). הסבר: n%2 = 1, ובהתאם מתקיים 3 ≤ 3 + 4 - 2.

בסעיף ג נתון אוטומט מחסנית דטרמיניסטי המקבל את L. כל המצבים, המעברים וסימני הקלט קיימים, אבל מלבד המעברים בין q0 ל-q1 חסרות בכל מעבר האות שבראש המחסנית והפעולה על המחסנית (המעברים האלה ממוספרים 1 עד 21), וגם המצבים המקבלים לא סומנו.

המעברים הנתונים במלואם (בין q0 ל-q1):

שאר המעברים, כפי שהם מצוירים בתרשים (חסרים בהם ראש המחסנית והפעולה):

(1)  q0  --b-->  q2          (8)   q1  --b-->  q4        (15)  q8  --c-->  q8
(2)  q2  --b-->  q3          (9)   q1  --c-->  q5        (16)  q7  --b-->  q10
(3)  q3  --b-->  q2          (10)  q4  --b-->  q7        (17)  q7  --c-->  q11
(4)  q3  --c-->  q6          (11)  q4  --c-->  q8        (18)  q8  --c-->  q11
(5)  q6  --c-->  q6          (12)  q5  --c-->  q8        (19)  q10 --b-->  q10
(6)  q3  --c-->  q9          (13)  q7  --b-->  q7        (20)  q10 --c-->  q11
(7)  q6  --c-->  q9          (14)  q7  --c-->  q8        (21)  q11 --c-->  q11

אוטומט מחסנית דטרמיניסטי (PDA) עבור השפה L, סעיף ג. מצבים q0-q11, כל המצבים והמעברים וסימני הקלט נתונים; חסרה בכל מעבר (חוץ מהמעברים בין q0 ל-q1) האות שבראש המחסנית והפעולה על המחסנית (למלא ע"י התלמיד). מעברים ממוספרים (1)-(21). מצבים מקבלים לא סומנו (למלא).

q0 --b(1)--> q2
q2 --b(2)--> q3 ; q3 --b(3)--> q2 (מעברים דו-כיווניים בין q2,q3)
q3 --c(4)--> q6
q6 self-loop c(5)
q6 --c(7)--> q9
q3 --c(6)--> q9 (קשת עליונה ישירה, עוקפת את q6)

q0 <-> q1 (מעברים דו-כיווניים, מסומנים במלואם - היחידים שבהם המחסנית מוגדרת):
  q0 -> q1: a, S / דחוף A
  q1 self/next: a, A / דחוף A
  q1 -> q0: a, S / דחוף ריקה מחסנית (טקסט מקורי; ראו הערת נאמנות)

q1 --b(8)--> q4
q4 --b(10)--> q7
q7 self-loop b(13)
q7 --b(16)--> q10
q10 self-loop b(19)
q1 --c(9)--> q5
q4 --c(11)--> q8
q7 --c(14)--> q8
q7 --c(17)--> q11
q10 --c(20)--> q11
q5 --c(12)--> q8
q8 self-loop c(15)
q8 --c(18)--> q11
q11 self-loop c(21)
[תיקון קריאה 04.09: המעברים הנתונים הם q0→q1: (a, מחסנית ריקה/דחוף S), (a, A/דחוף A); q1→q0: (a, S/דחוף A), (a, A/דחוף A) — ראו pda_q8.py]