TAILIEUCHUNG - Lý thuyết văn phạm, ngôn ngữ và ôtômát - Chương 4

Tài liệu tham khảo bài giảng Lý thuyết văn phạm, ngôn ngữ và ôtômát gồm 4 chương - Chương 4 Otomat đẩy xuống | c Ẳtttmcị i - lẲbệẨẦ cẲLtnty Như ta đã biết trong chưong 3 văn phạm chính quy tưong đưong với ôtômat hữu hạn. Trong chương này ta sẽ nghiên cứu ôtômat đẩy xuống sự khác biệt chủ yếu giữa ôtômat đẩy xuống với ôtômat hữu hạn là ôtômat đẩy xuống có thêm một ngăn xếp chứa các ký tự theo kiểu Last in First out tức là phần tử mới được đưa vào sẽ được xếp trên phần tử trước đó và do đó nó được đưa ra trước. Chính sự khác biệt đó đã giúp ôtômat đẩy xuống đoán nhận được ngôn ngữ phi ngữ cảnh mà ôtômat hữu hạn không làm được. Phần cuối chương này đề cập tới vấn đề kiểm tra xem một xâu có thuộc ngôn ngữ sinh bởi văn phạm đã cho hay không. Đây là một bài toán rất khó đối với một văn phạm bất kỳ nhưng đối với văn phạm LL1 thì ta có thuật toán phân tích tất định để trả lời câu hỏi đó. Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - p. 179 201 Định nghĩa. Một ôtômat đẩy xuống PA là một bộ gồm 7 thành phần M E Q Ạ ổ Ợo5 2 h trong đó - E là tập hữu hạn khác rỗng các ký tự đầu vào bảng chữ cái . - Q là tập hữu hạn khác rỗng các trạng thái sao cho E A Q 0. - K tập hữu hạn khác rỗng các ký tự của ngăn xếp. - ZQ e K là ký hiệu đầu tiên của danh sách đẩy xuống. F G Q là tập trạng thái kết thúc. ổ là hàm chuyển của M cỏ hai dạng Nếu ỏ là ánh xạ E u A X Q X K Q X K thì M được gọi là ôtômat đẩy xuống đơn định. Nếu ô là ánh xạ E u A X Q X K thì M được gọi là ôtômat không đơn định. Trong chương này ta chỉ nghiên cứu ôtômat không đơn định và ký hiệu là PA Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - p. 180 201 Ví dụ 1. Cho ôtômat đẩy xuống Ml E Q K. ổ Ợo F trong đó E . ợo Qi K a b z0 Hàm chuyển ỏ được xác định như sau ỏ a q0 Zũ 70 0 ổ a Qo a 7o a ỗ b qữ à 71 A F 21 Ví dụ 2. Cho ôtômat đẩy xuống M2 E Q K. ổ Ợo F trong đó S 0 l c Q 7o 71 42 K 0 1 c z0 F ợ2 Hàm chuyển ỏ được xác định như sau - ổ a Ợcb k ợcb ka Va e E c v c e

• Ngôn ngữ học
• Lý thuyết văn phạm
• ngôn ngữ hình thức
• ôtômát hữu hạn
• otomat đẩy xuống
• văn phạm phi ngữ cảnh
• Tin học lý thuyết
• Bài giảng Tin học lý thuyết
• Context Free Grammar
• Giản lược văn phạm phi ngữ cảnh
• Chuẩn hóa văn phạm phi ngữ cảnh
• Luận văn Thạc sĩ
• Tóm tắt Luận văn Thạc sĩ
• Luận văn Thạc sĩ Sư phạm Lịch sử
• Sư phạm Lịch sử
• Phương pháp dạy học môn Lịch sử
• Vận dụng lý thuyết đa thông minh
• Lý thuyết đa thông minh trong dạy môn Sử 10
• Lý thuyết Structuration của A
• Giddens
• Lý thuyết Structuration
• Bối cảnh ra đời lý thuyết Structuration
• Nội dung lý thuyết Structuration
• Đánh giá lý thuyết Structuration
• Lý thuyết xã hội học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Ôtômat hữu hạn
• Bài giảng Lý thuyết thông tin
• Lý thuyết thông tin
• Xử lý tín hiệu
• Lý thuyết thông tin thống kê
• Đô lượng thông tin
• Entropy có điều kiện
• Văn phạm chính quy
• Sự tương đương giữa RG và FA
• Tập hợp chính quy
• Regular Grammar
• Ngôn ngữ chính quy
• Lý thuyết automat
• Bài giảng Lý thuyết automat
• Biểu diễn ngôn ngữ
• Automat hữu hạn
• Văn phạm chính qui
• Luận văn Thạc sĩ ngành Mĩ thuật
• Lý luận và phương pháp dạy học bộ môn Mĩ thuật
• Mĩ thuật học
• Dạy học phân môn lý thuyết âm nhạc
• Vai trò phân môn lý thuyết âm nhạc
• Biện pháp dạy học phân môn lý thuyết âm nhạc
• Luận văn thạc sĩ Âm nhạc
• Lý luận và Phương pháp dạy học Âm nhạc
• Lý thuyết Âm nhạc cơ bản
• Phương pháp thuyết trình nhóm
• Sử dụng phương pháp thuyết trình nhóm
• Lý luận dạy học Hóa học đại cương
• Dạy học Hóa học đại cương
• Phương pháp dạy học tích cực
• Sư phạm Hóa học
• Tổng quan lý thuyết tính toán
• Khái niệm ngôn ngữ
• Khái niệm văn phạm
• Các phép toán trên ngôn ngữ
• Cơ sở lý thuyết tập hợp và lôgic toán
• Cơ sở lý thuyết tập hợp
• Bài giảng Cơ sở lý thuyết tập hợp
• Cơ sở lôgic toán
• Quy tắc suy luận
• Giáo trình Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ
• Ngôn ngữ lập trình
• Văn phạm hình thức
• Luận văn Thạc sĩ Khoa học xã hội
• Văn học Việt Nam
• Tiểu thuyết lịch sử
• Phạm Minh Kiên
• Tiền Lê vận mạt
• Trần Hưng Đạo
• Nghiên cứu tôn giáo
• Xã hội học trong nghiên cứu tôn giáo
• Thuyết cấu trúc chức năng
• Thuyết mâu thuẫn
• Thuyết trao đổi
• Lý thuyết phân tích văn hóa
• luận văn
• lý thuyết ánh sáng
• lượng tử ánh sáng
• ứng dụng dạy học 12
• thực nghiệm sư phạm
• tâm lý sư phạm
• Nguyên lý thống kê kinh tế
• Giáo trình Nguyên lý thống kê kinh tế
• Bài giảng Nguyên lý thống kê kinh tế
• Lý thuyết Nguyên lý thống kê kinh tế
• Tài liệu Nguyên lý thống kê kinh tế
• Học Nguyên lý thống kê kinh tế