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

Bài giảng Lý thuyết tính toán: Bài 6 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về văn phạm phi ngữ cảnh; khái niệm văn phạm phi ngữ cảnh; định nghĩa hình thức; văn phạm nhập nhằng; dạng chuẩn tắc Chomsky; cây dẫn xuất; . 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 6 VĂN PHẠM PHI NGỮ CẢNH 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. Văn phạm nhập nhằng 4. Dạng chuẩn tắc Chomsky 1 Khái niệm Khái niệm Văn phạm phi ngữ cảnh Context-free Grammar CFG CFG Là một phương pháp mạnh hơn để mô tả ngôn ngữ Ứng dụng - Bộ biên dịch trong các ngôn ngữ lập trình - Bộ phân tích trong các trình biên dịch và thông dịch Ví du E E T T T T F F F E a 2 Khái niệm Một văn phạm gồm có Tập các quy tắc thay thế các sản xuất Mỗi quy tắc là một dòng bao gồm 1 ký hiệu và 1 xâu được ngăn cách bởi dấu mũi tên Ký hiệu biến Các ký hiệu in hoa Ký hiệu kết thúc Các ký hiệu in thường số hoặc ký tự đặc biệt Biến ban đầu thường xuất hiện bên trái của quy tắc trên cùng 3 Ví dụ E E T T T T F F F E a Dẫn xuất E E T T T F T a T a F a E a T a T F a F F a a F a a a Cũng có thể viết E a a a E a E a T a a a 4 Ví dụ Dẫn xuất trái nhất Luôn lựa chọn dẫn xuất ở bên trái . . . F T a T . . . a a a Dẫn xuất phải nhất Luôn lựa chọn dẫn xuất ở bên phải . . . F T F F . . . a a a 5 Cây dẫn xuất E E T T F F E a T T x F F a a 6 Định nghĩa hình thức Định nghĩa hình thức CFG G V Σ R S Trong đó V là tập hữu hạn gồm các biến Σ là tập hữu hạn các ký hiệu kết thúc Σ 6 V R tập các quy tắc S biến bắt đầu 7 Định nghĩa hình thức Định nghĩa 1 Ngôn ngữ của văn phạm là w w Σ và S w Định nghĩa 2 Một ngôn ngữ phi ngữ cảnh CFL là ngôn ngữ được tạo ra bởi một văn phạm phi ngữ cảnh CFG 8 Ví dụ CFL S S SS ε A ε . . . Ngôn ngữ B 0n 1n n 0 S ε S 0S1 9 Ví dụ Cho CFG sau a a a E E E Mỗi cây dẫn xuất đều có duy E E nhất một cây dẫn xuất trái nhất E và duy nhất một cây dẫn xuất a phải nhất E E E E E E E E a a E E a a a a 10 Văn phạm nhập nhằng Ngôn ngữ nhập nhằng Chuỗi nhập nhằng Có nhiều hơn 2 cây dẫn xuất Có nhiều cách để tạo ra chuỗi đó Văn phạm nhập nhằng Một văn phạm là nhập nhằng nếu một vài chuỗi có thể được sinh ra bởi nhiều cách 11 Ví dụ Văn phạm không nhập nhằng Văn phạm nhập nhằng E E T E E E T E E T

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Văn phạm phi ngữ cảnh
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• giáo trình lý thuyết tính toán
• tài liệu về lý thuyết tính toán
• học lý thuyết tính toán
• tự học lý thuyết tính toán
• 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ở 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
• Quy dẫn
• Bài toán không quyết định được
• Quy dẫn thông qua lịch sử tính toán
• Bài toán PCP
• Quy dẫn ánh xạ
• Ôtômat đẩy xuống
• Mô hình tính toán
• Ngôn ngữ không phi ngữ cảnh
• Ngôn ngữ phi ngữ cảnh
• Định nghĩa giải thuật
• Bài toán của Hilbert
• Luận đề Church Turing
• Ngôn ngữ quyết định được
• Bài toán quyết định được
• Ngôn ngữ chính quy
• Bài toán dừng
• Máy Turing vạn năng
• Phương pháp chéo hóa
• Ngôn ngữ vạn năng
• Bài giảng Lý thuyết hạch toán kế toán
• Lý thuyết hạch toán kế toán
• Hệ thống phương pháp hạch toán kế toán
• Phương pháp chứng từ
• Phương pháp tính giá
• Phương pháp tổng hợp cân đối
• Quy hoạch tuyến tính
• Lý thuyết quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài toán vận tải
• Tính chất của ngôn ngữ chính quy
• Ngôn ngữ không chính quy
• Nhận biết ngôn ngữ không chính quy
• Thiết kế ôtômat hữu hạn
• Toán tử chính quy
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Biểu thức chính quy
• Ngôn ngữ của biểu thức chính quy
• Toán học cơ sở
• Máy trừu tượng
• Biểu diễn ngôn ngữ
• Cấu trúc rời rạc
• Văn phạm và ô tô mát
• Kiến thức cơ bản về ngôn ngữ
• Phương pháp phân tích từ vựng
• Phân tích cú pháp
• Automat hữu hạn
• Accepter hữu hạn đơn định
• Accepter hữu hạn không đơn định
• Rút gọn số trạng thái
• Văn phạm chính quy
• Quan hệ ngôn ngữ và biểu thức chính quy
• Ngôn ngữ lập trình
• Biến đổi văn phạm
• Dạng chuẩn quan trọng
• Giải thuật thành viên
• Tập hợp
• Đồ thị
• Boolean logic
• Quan hệ tương đương
• Độ dài dẫn xuất
• Bổ đề Bơm (Pumping Lemma)
• Máy Turing
• Ngôn ngữ của Turing Machine
• Cấu trúc dữ liệu Turing Machine
• Đoán nhận ngôn ngữ
• Các biến thể của máy Turing
• Máy Turing tùy chọn tại chỗ
• Máy Turing bán vô hạn
• Máy Turing đa băng
• Máy Turing không đơn định