- BÀI 11: 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.
- 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ể.
- 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ữ.
- B là 1 DFA chấp thuận xâu vào w}.
- Định lý 1.
- A DFA là ngôn ngữ quyết định được.
- Đưa ra một TM quyết định A DFA.
- TM sẽ kiểm tra xem B có biểu diễn đúng định dạng không.
- 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ỏ.
- Định lý 2.
- A NFA là ngôn ngữ quyết định được.
- Phương pháp 1: Đưa ra một TM quyết định A NFA tương tự Định lý 1.
- Chuyển NFA B thành DFA C tương đương.
- Chạy máy Turing M giống Định lý 1 với xâu đầu vào <C,w>.
- 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ỏ.
- Định lý 3.
- A REX là ngôn ngữ quyết định được.
- 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 <A,w>.
- 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.
- Một số bài toán ngôn ngữ khác.
- Bài toán chấp thuận.
- Bài toán kiểm tra rỗng (Emptiness Testing) E DFA.
- Bài toán kiểm tra tương đương (Equality Testing) EQ DFA.
- Bài toán kiểm tra rỗng (Emptiness Testing).
- Định lý 4.
- E DFA là ngôn ngữ quyết định được.
- Bác bỏ.
- Nếu không có → Chấp thuận.
- Tương đương với bài toán đánh dấu đồ thị.
- Thuật toán cho TM T quyết định E DFA.
- Trên đầu vào <A>.
- Đánh dấu trạng thái ban đầu A.
- Lặp lại bước sau cho đến khi không còn trạng thái đánh dấu:.
- Đánh dấu các trạng thái có một bước chuyển tới nó từ một trạng thái đã được đánh dấu.
- Nếu không có trạng thái chấp thuận nào được đánh dấu → Chấp thuận, ngược lại bác bỏ.
- Bài toán kiểm tra tương đương (Equality Testing) Định lý 5.
- EQ DFA là ngôn ngữ quyết định được.
- Xây dựng DFA C chấp thuận tập khác biệt đối xứng của L(A) và L(B).
- Sử dụng bài toán kiểm tra rỗng để quyết định EQ DFA.
- Bài toán kiểm tra tương đương (Equality Testing).
- Thuật toán cho TM F quyết định EQ DFA.
- Chạy máy Turing T giống Định lý 4 đối với xâu đầu vào <C>.
- Nếu T chấp thuận thì F chấp thuận, ngược lại F bác bỏ.
- Bài toán: Liệu 1 văn phạm phi ngữ cảnh CFG có sinh ra 1 xâu w nào đó hay không.
- Định lý 6.
- A CFG là ngôn ngữ quyết định được.
- Bài toán kiểm tra CFG.
- Nếu có một dẫn xuất nào đó sinh ra w thì chấp thuận, ngược lại thì bác bỏ.
- Do CFG → PDA nên tính quyết định của PDA cũng tương tự như CFG.
- Bài toán kiểm tra CFG sinh ra chuỗi rỗng.
- Bài toán: Liệu 1 văn phạm phi ngữ cảnh CFG có thể không sinh ra được một xâu nào hay không.
- Định lý 7.
- E CFG là ngôn ngữ quyết định được.
- Ý TƯỞNG: Kiểm tra xem liệu biến bắt đầu có tạo ra được một.
- Đánh dấu tất cả các ký hiệu kết thúc trong G.
- Lặp lại bước sau cho đến khi không còn biến mới được đánh dấu:.
- Đánh dấu một biến A nào đó khi G có một dẫn xuất A → U 1 U 2.
- U k đã được đánh dấu.
- Nếu biến khởi đầu chưa được đánh dấu thì chấp thuận, ngược lại bác bỏ.
- Bài toán kiểm tra CFG tương đương.
- Liệu ta có thể chứng minh tương tự Định lý 5?