tailieunhanh - Bài giảng Lý thuyết tính toán: Bài 7 - Phạm Xuân Cường

Bài giảng Lý thuyết tính toán: Bài 7 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về ôtômat đẩy xuống; khái niệm ôtômat đẩy xuống; định nghĩa hình thức; sự tương đương với CFG; biểu đồ trạng thái của PDA; ngôn ngữ không phi ngữ cảnh; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 7 Ôtômat đẩy xuống Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Khái niệm 2. Định nghĩa hình thức 3. Sự tương đương với CFG 4. Ngôn ngữ không phi ngữ cảnh 1 Khái niệm Khái niệm Ôtômat đẩy xuống Push down automata PDA PDA Là một mô hình tính toán giống với NFA ngoại trừ một thành phần mở rộng được gọi là ngăn xếp Ngăn xếp Là một cấu trúc dữ liệu hoạt động theo cơ chế LIFO - Các phương thức read push ignored pop ignored PDA CFG về sức mạnh Thêm công cụ hữu ích khi đoán nhận một ngôn ngữ phi ngữ cảnh 2 Biểu diễn hình học của PDA FSM PDA a a b c Trong đó a là ký tự vào b là ký tự nằm ở đỉnh ngăn xếp ký tự này sẽ được lấy ra pop c là ký tự được đẩy push vào trong ngăn xếp a b c đều có thể nhận ký tự ε - Nếu b ε ngăn xếp đang rỗng hoặc chưa được đọc - Nếu c ε không có gì được đẩy vào ngăn xếp 3 Ví dụ PDA Xét ngôn ngữ A 0n 1n n 0 Σ 0 1 Bộ chữ đầu vào Γ ε Bộ chữ ngăn xếp Ký tự dùng để xác định đáy của ngăn xếp ε ε ε ε ε ε ε start A B C D 0 ε 0 1 0 ε 4 PDA hoạt động như thế nào Khi nào 1 chuỗi được chấp thuận Tồn tại 1 đường đi từ trạng thái bắt đầu đến trạng thái chấp thuận trong bộ điều khiển trạng thái Đến cuối xâu sẽ đọc hết các ký tự và không còn ký tự nào trong ngăn xếp Chú ý a b c a ε c Lấy b từ ngăn xếp ra Không lấy gì từ ngăn xếp ra 5 Định nghĩa hình thức Định nghĩa hình thức Ôtômat đẩy xuống bộ 6 hay 6 chiều M Q Σ Γ δ q0 F Trong đó - Q Tập trạng thái hữu hạn - Σε Bộ chữ đầu vào tập hữu hạn các ký tự - Γ Bộ chữ của ngăn xếp tập hữu hạn các ký tự - δ Hàm dịch chuyển δ Q x Σε x Γε P Q x Γε - q0 Trạng thái bắt đầu q0 Q - F Là tập các trạng thái kết thúc F Q 6 Ví dụ PDA theo định nghĩa hình thức ε ε ε ε ε ε ε start A B C D 0 ε 0 1 0 ε δ Σ 0 1 ε Q A B C D Γ 0 ε 0 ε 0 ε Σ 0 1 A B Γ 0 B B 0 C ε F D C C ε D ε D Tất cả các ô trống đều biểu thị Ø 7 Sự tương đương với CFG Sự tương đương với CFG Nhắc lại Một ngôn ngữ phi ngữ cảnh là ngôn ngữ được biểu diễn bởi một CFG nào đó Định lý 1 Một ngôn ngữ là phi ngữ cảnh .