Bài giảng Lý thuyết tính toán: Bài 11 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về các ngôn ngữ quyết định được; các bài toán quyết định được với ngôn ngữ chính quy; các bài toán quyết định được với ngôn 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 11 Các ngôn ngữ quyết định được Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Giới thiệu 2. Các bài toán quyết định được với ngôn ngữ chính quy 3. Các bài toán quyết định được với ngôn ngữ phi ngữ cảnh 1 Giới thiệu Giới thiệu Tính quyết định giúp chúng ta nghiên cứu kỹ hơn về khả năng giải quyết các bài toán của thuật toán Một số bài toán có thể giải được bằng thuật toán một số thì không thể Cần phải nghiên cứu về khả năng không giải quyết được Mục đích là để phát hiện ra giới hạn về tính giải được của thuật toán 2 Các bài toán quyết định được với ngôn ngữ chính quy Bài toán Bài toán Cho một DFA và một chuỗi w DFA có chấp thuận chuỗi w không Đây có phải là một bài toán quyết định không Để trả lời câu hỏi ta cần đưa bài toán về bài toán ngôn ngữ ADFA B là 1 DFA chấp thuận xâu vào w 3 Định lý 1 ADFA là ngôn ngữ quyết định được Chứng minh Đưa ra một TM quyết định ADFA TM sẽ nhận chuỗi đầu vào là TM sẽ kiểm tra xem B có biểu diễn đúng định dạng không TM sẽ mô phỏng B trên chuỗi w Nếu B đạt được trạng thái chấp thuận thì TM sẽ chấp thuận ngược lại thì bác bỏ TM sẽ luôn luôn dừng always halt 4 Định lý 2 ANFA là ngôn ngữ quyết định được Chứng minh Phương pháp 1 Đưa ra một TM quyết định ANFA tương tự Định lý 1 Phương pháp 2 1. Chuyển NFA B thành DFA C tương đương 2. Chạy máy Turing M giống Định lý 1 với xâu đầu vào 3. Nếu M chấp thuận thì kết luận N chấp thuận ngược lại N bác bỏ 5 Định lý 3 AREX là ngôn ngữ quyết định được Chứng minh 1. Biến đổi biểu thức chính quy R thành NFA A tương đương 2. Chạy máy Turing M giống Định lý 2 với xâu đầu vào 3. Nếu M chấp thuận thì kết luận R chấp thuận ngược lại R bác bỏ Khả năng quyết định được của máy Turing biểu diễn bởi DFA NFA hay RE đều tương đương 6 Một số bài toán ngôn ngữ khác Bài toán chấp thuận ADFA B là 1 DFA chấp thuận xâu vào w Bài toán kiểm tra rỗng Emptiness Testing EDFA A là 1 DFA và L A Ø Bài toán kiểm tra tương đương Equality Testing EQDFA A B là DFA và L A L
