บทความนี้อธิบายการสร้าง PDA สำหรับภาษาที่:
- จำนวน 0 = จำนวน 3
- จำนวน 1 = จำนวน 2
- m,n ≥ 0 (รวมสตริงว่าง)
State และ Transition
q₀: เริ่มต้น รับ 0 และ 1
- (0, I/0I) → q₀: push 0
- (0, 0/00) → q₀: push 0
- (1, 0/10) → q₁: push 1 บน 0
- (1, I/1I) → q₅: เริ่มจาก 1 (m>0, n=0)
- (3, 0/ε) → q₃: pop 0 สำหรับ 3
- ($, I/I) → q₄: สตริงว่าง
q₁: รับ 1 ต่อ
- (1, 1/11) → q₁: push 1
- (2, 1/ε) → q₂: pop 1 สำหรับ 2
q₂: pop 1 สำหรับ 2 แล้ว pop 0 สำหรับ 3
- (2, 1/ε) → q₂
- (3, 0/ε) → q₃
q₃: pop 0 สำหรับ 3
- (3, 0/ε) → q₃
- ($, I/I) → q₄ (accept)
q₅: กรณีเริ่มจาก 1 (n=0)
- (1, 1/11) → q₅
- (2, 1/ε) → q₆
q₆: pop 1 สำหรับ 2
- (2, 1/ε) → q₆
- ($, I/I) → q₄ (accept)
สตริงที่ยอมรับได้
- 0ⁿ3ⁿ: 03, 0033, 000333...
- 1ᵐ2ᵐ: 12, 1122, 111222...
- 0ⁿ1ᵐ2ᵐ3ⁿ: 0123, 001233, 011223...
- สตริงว่าง
หมายเหตุ: เป็นการอธิบายทฤษฎี ไม่มีโค้ด C++ ที่ executable
