ภาษาที่: จำนวน 1 = จำนวน 0 + จำนวน 2
State และ Transition
q₀: รับ 0 และ 1 เริ่มต้น
- (0, I/0I) → q₀: push 0
- (0, 0/00) → q₀: push 0
- (1, I/1I) → q₁: push 1 (กรณี m=0)
- (1, 0/ε) → q₁: pop 0 สำหรับ 1 (จับคู่ 0 กับ 1)
q₁: รับ 1 ต่อ และ 2
- (1, 1/11) → q₁: push 1 (ส่วนเกินของ 1)
- (1, 0/ε) → q₁: pop 0 สำหรับ 1 (ยังมี 0 เหลือ)
- ($, I/I) → qf: accept (กรณี 0ᵐ1ᵐ)
- (2, 1/ε) → q₂: pop 1 สำหรับ 2
q₂: pop 1 สำหรับ 2
- (2, 1/ε) → q₂
- ($, I/I) → qf: accept
สตริงที่ยอมรับได้
- 0ᵐ1ᵐ: 01, 0011, 000111... (n=0)
- 1ⁿ2ⁿ: 12, 1122, 111222... (m=0)
- 0ᵐ1ᵐ⁺ⁿ2ⁿ: 0112, 001112... (m,n>0)
- สตริงว่าง
หลักการ: ใช้ stack นับ 0 แล้ว pop ตรง 1 แล้ว push 1 ที่เหลือ แล้ว pop ตรง 2
