Giáo trình Kiến trúc máy tính và
Hệ điều hành 145
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat đẩy xuống (PDA)
Ngôn ngữ được đoán nhận PDA
Sự tương đương giữa PDA và văn phạm phi
ngữ cảnh
Ôtômat đẩy xuống đơn định
Giáo trình Kiến trúc máy tính và
Hệ điều hành 146
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
01011
1. Ôtômat đẩy xuống
(Push Down Automat -
PDA)
1.1. Mô tả Băng vào
qBộ điều khiển
Đầu đọc
Ngăn xếp
Giáo trình Kiến trúc máy tính và
Hệ điều hành 147
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Ôtômat đẩy xuống
1.1. Mô tả
Tại một thời điểm bộ điểu khiển:
•Trạng thái q
•Đọc một ký hiệu trên băng vào (: k0 đọc)
•Nhìn ký hiệu ở đỉnh ngăn xếp
xác định trạng thái tiếp theo và quyết định hành
động liên quan đến ngăn xếp
Giáo trình Kiến trúc máy tính và
Hệ điều hành 148
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Ôtômat đẩy xuống
1.1. Mô tả
Có 2 cách để ôtômát đẩy xuống đoán nhận xâu
vào:
•Đọc xong xâu vào và ôtômat ở trạng thái kết
thúc
•Đọc xong xâu vào và ngăn xếp rỗng
Giáo trình Kiến trúc máy tính và
Hệ điều hành 149
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Ôtômat đẩy xuống
1.2. Định nghĩa: M(Σ, Q, , z, δ, q0, F)
Σ: bộ chữ vào
Q: tập hữu hạn các trạng thái
q0 Q: trạng thái đầu
F Q: tập các trạng thái kết thúc
: tập ký hiệu trên ngăn xếp
z : ký hiệu đầu tiên ở đỉnh ngăn xếp
δ: hàm chuyển trạng thái dạng δ(q,a,x)={(p, )} Với
q,p Q, a Σ{}, x , *