tailieunhanh - Bài giảng Ngôn ngữ hình thức: Chương 4 - Nguyễn Thị Hồng

Bài giảng Ngôn ngữ hình thức: Chương 4 Ôtômat đẩy xuống, cung cấp cho người học những kiến thức như: Ô tô mát đẩy xuống; Sự tương đương giữa các loại ô tô mát đẩy xuống; Mối quan hệ giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh; Ngôn ngữ phi ngữ cảnh. Mời các bạn cùng tham khảo! | Chương 4 Ôtômat đẩy xuống GV Nguyễn Thi Hô ̣ ̀ng Email nguyenhong@ Nội dung Ô tô mát đẩy xuống Sự tương đương giữa các loại ô tô mát đẩy xuống Mối quan hệ giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh Ngôn ngữ phi ngữ cảnh Ô tô mát đẩy xuống ODX Mô tả trực quan Ô tô mát đẩy xuống Cấu tạo Một băng vào chứa các kí hiệu của xâu vào Một đầu đọc duyệt băng từ trái qua phải Một bộ điều khiển các trạng thái hữu hạn Một stack có khả năng nhớ vô hạn lúc đầu là rỗng lúc đầu stack chứa một kí hiệu đặc biệt để đánh dấu đáy stack Hoạt động của Ô tô mát đẩy xuống Ban đầu stack là rỗng Quá trình thực hiện của ô tô mát đẩy xuống tương tự như ô tô mát hữu hạn không tiền định Mỗi bước thực hiện của Ô tô mát đẩy xuống căn cứ vào ba yếu tố Kí hiệu ở đỉnh stack Trạng thái của ô tô mát Kí hiệu đọc được trên băng vào Hoạt động của Ô tô mát đẩy xuống Mỗi dịch chuyển gồm các hành động Thay đổi nội dung stack đỉnh stack Thay đổi trạng thái Đầu đọc dịch sang phải một ô Chú ý tồn tại dịch chuyển nghĩa là kí hiệu trên băng không được tham khảo đầu đọc không dịch chuyển sang phải Sự đoán nhận của ODX Có hai cách thừa nhận xâu Xâu vào được thừa nhận khi ô tô mát đọc hết xâu và đến một trạng thái thừa nhận Xâu vào được thừa nhận khi ô tô mát đọc hết xâu và lúc đó stack rỗng. Ô tô mát đẩy xuống Định nghĩa Ô tô mát đẩy xuống không tiền định là một bộ 7 thành phần M Σ Q Γ δ q0 Z0 F Q tập hữu hạn các trạng thái Σ bộ chữ vào Γ bộ chữ cái Stack Q Γ Ø δ hàm chuyển Γ x Q x Σ ε tập con của Q x Γ q0 trạng thái khởi đầu Z0 ký hiệu bắt đầu trên Stack đáy stack F Q tập các trạng thái kết thúc Ô tô mát đẩy xuống Ta gọi hình trạng của ô tô mát đẩy xuống là mọi xâu có dạng qw trong đó Γ q Q w Hình trạng có dạng Z0q0x được gọi là hình trạng ban đầu Hệ viết lại ngầm định trong M là W V P V Q Γ P p δ z q a hay zqa p là một quy tắc trong P Ô tô mát đẩy xuống Ngôn ngữ được thừa nhận theo trạng thái cuối bởi ODX M là L M w Z0q0w gt M p Γ p F Ngôn ngữ được thừa nhận theo stack rỗng bởi ODX M là N M