บทความนี้อธิบายการสร้าง Pushdown Automaton (PDA) สำหรับภาษาที่มีเงื่อนไข:
- จำนวน 'a' = 2 × จำนวน 'b'
- จำนวน 'c' = 4 × จำนวน 'd'
- m,n ≥ 0 (รวมสตริงว่าง)
องค์ประกอบของ PDA
- Input tape
- Control unit (states)
- Stack ขนาดไม่จำกัด
PDA เป็น 7-tuple: (Q, Σ, S, δ, q₀, I, F)
การออกแบบ State และ Transition
State q₀: เริ่มต้น รับ a และ c
- (a, I/aI) → q₀: push a
- (c, I/cI) → q₀: push c
- (a, a/aa) → q₀: push a
- (c, c/cc) → q₀: push c
- (b, a/ε, pop 2a) → q₃: เริ่ม pop a สำหรับ b
- (c, a/ca) → q₁: เปลี่ยนไปรับ c
- (d, c/ε, pop 4c) → q₄: เริ่ม pop c สำหรับ d
- ($, I/I) → q₅: สตริงว่าง
State q₁: รับ c ต่อ
- (c, c/cc) → q₁
- (d, c/ε, pop 4c) → q₂
State q₂: pop c สำหรับ d แล้วไป pop a สำหรับ b
- (d, c/ε, pop 4c) → q₂
- (b, a/ε, pop 2a) → q₃
State q₃: pop a สำหรับ b
- (b, a/ε, pop 2a) → q₃
- ($, I/I) → q₅ (accept)
State q₄: pop c สำหรับ d จนหมด
- (d, c/ε, pop 4c) → q₄
- ($, I/I) → q₅ (accept)
State q₅: Accept state
สตริงที่ยอมรับได้
- c⁴ⁿdⁿ: ccccd, ccccccccdd, ...
- a²ᵐbᵐ: aab, aaaabb, ...
- a²ᵐc⁴ⁿdⁿbᵐ: aaccccdb, aaaaccccccccddbb, ...
- สตริงว่าง (ε)
หมายเหตุ: บทความนี้เป็นทฤษฎี ไม่มีโค้ด C++ ที่รันได้จริง เนื่องจาก PDA เป็นแบบจำลองทางทฤษฎี
