Xây dựng PDA cho ngôn ngữ: số 'a' gấp đôi 'b', số 'c' gấp 4 lần 'd'. Chuỗi rỗng cũng được chấp nhận.
Cấu trúc PDA
- Input tape, control unit, stack vô hạn.
- 7-tuple: (Q, Σ, S, δ, q0, I, F)
Các trạng thái và chuyển trạng thái chính
- q0: Đọc 'a' đẩy vào stack; đọc 'c' đẩy vào stack; gặp 'b' khi đỉnh stack là 'a' thì pop 2 'a' chuyển q3; gặp 'd' khi đỉnh stack là 'c' thì pop 4 'c' chuyển q4; chuỗi rỗng chuyển q5.
- q1: Tiếp tục đẩy 'c'; gặp 'd' pop 4 'c' chuyển q2.
- q2: Tiếp tục pop 'c' cho 'd'; gặp 'b' pop 2 'a' chuyển q3.
- q3: Pop 2 'a' cho mỗi 'b'; chuỗi rỗng chuyển q5.
- q4: Pop 4 'c' cho 'd'; chuỗi rỗng chuyển q5.
- q5: Trạng thái chấp nhận.
Lưu ý: Bài viết mô tả lý thuyết PDA, không cung cấp mã C++ mô phỏng chạy.