CHƯƠNG TRÌNH DỊCH BÀI 4: XÂY DỰNG DFA Nội dung Automat hữu hạn (FA) Đồ thị chuyển (transition diagram - TD) Automat hữu hạn không đơn định (NFA) Automat hữu hạn đơn định (DFA) Chuyển đổi từ biểu thức quy sang NFA Chuyển đổi từ NFA sang DFA DFA tối ưu cho phân tích từ vựng Bộ phân tích từ vựng dựa DFA Bài tập TRƯƠNG XUÂN NAM Phần Automat hữu hạn (FA) TRƯƠNG XUÂN NAM Automat hữu hạn (FA)  Trong tập phần trước, xem xét PTTV đơn giản, số đặc điểm dễ nhận thấy từ thiết kế này:  Cấu trúc chương trình đơn giản, dễ hiểu  Dễ mở rộng bổ sung từ loại  Hoạt động chậm, từ loại thử đốn nhận lần; trường hợp tệ (có lỗi) có độ phức tạp cao phải thử tất từ loại  Trong phần thảo luận thiết kế khắc phục vấn đề tốc độ dựa ý tưởng xây dựng đoán nhận với lần thử TRƯƠNG XUÂN NAM Automat hữu hạn (FA)  Automat hữu hạn (finite-state automaton) dùng để đốn nhận lớp ngơn ngữ quy  Cấu trúc học FA gồm: Automat  Quá trình hoạt động:     Xâu vào hữu hạn  Bảng chuyển  Đầu đọc  Xâu vào Bảng chuyển Bắt đầu từ trạng thái xuất phát Đọc từ kí tự từ xâu vào Quan sát bảng chuyển để biết chuyển sang trạng thái Dừng kết thúc xâu vào trả trạng thái đoán nhận TRƯƠNG XUÂN NAM Automat hữu hạn (FA)  Hoạt động automat hữu hạn đơn giản:  Mỗi bước đọc kí tự từ đầu vào  Từ trạng thái bắt đầu, dựa kí tự đầu vào biến đổi trạng thái, q trình kết thúc đến trạng thái dừng  Trạng thái dừng định từ loại mà FA đoán nhận (bao gồm lỗi)  Dễ thấy độ phức tạp tính tốn thuật tốn đốn nhận tuyến tính theo độ dài liệu đầu vào (vì bước chuyển nhận kí tự đầu vào)  Vấn đề automat hữu hạn: làm xây dựng bảng chuyển hiệu TRƯƠNG XUÂN NAM Automat hữu hạn (FA)  Automat hữu hạn chia làm loại:  Automat hữu hạn đơn định (deterministic finite automata – DFA) • Với kí hiệu đầu vào, chuyển sang tối đa trạng thái thái (hoặc dừng báo lỗi) • Khơng chấp nhận kí hiệu đầu vào   Automat hữu hạn không đơn định (non-deterministic finite automata – NFA) • Chấp nhận kí hiệu đầu vào  • Với kí hiệu đầu vào, chuyển sang nhiều trạng thái  Hai loại automat tương đương khả đoán nhận ngơn ngữ chuyển đổi qua lại lẫn TRƯƠNG XUÂN NAM Phần Đồ thị chuyển (transition diagram) TRƯƠNG XUÂN NAM Đồ thị chuyển  Đồ thị chuyển phương pháp thường sử dụng để mô tả cách trực quan sơ đồ hoạt động automat hữu hạn Đồ thị chuyển biểu diễn tên Đồ thị chuyển biểu diễn số nguyên dương Đồ thị chuyển biểu diễn loại số thực TRƯƠNG XUÂN NAM Các kí hiệu đồ thị chuyển  Trạng thái: vẽ vịng trịn, kí hiệu ghi bên “tên” (số hiệu) trạng thái  Trạng thái kết thúc: vòng tròn kép  Trạng thái kết thúc có đánh dấu (*): ký tự cuối khơng thuộc vào từ tố đốn nhận  Bước chuyển: vẽ mũi tên nối tới trạng thái chuyển đến, kí hiệu ghi bên cạnh “nhãn” bước chuyển  Nhãn ghi kí tự loại kí tự cho phép thực bước chuyển  Nhãn “start”: xác định trạng thái bắt đầu automat TRƯƠNG XN NAM 10 Tối ưu NFA  Khơng có nhiều hội cho tối ưu NFA, ý tưởng dễ thấy hợp trạng thái start chu trình   Trong NFA trên: trạng thái ghép đơi  Trong NFA dưới:  Trạng thái ghép đôi  Sửa đổi hàm move(2, c) = start thành move(2, c) = TRƯƠNG XUÂN NAM a c ε ε ε ε ε ε b a ε c ε 31 Tối ưu DFA  Ý tưởng: ghép trạng thái tương đương (hàm move giống nhau) b  Ví dụ: xét DFA đoán nhận b*ab*a b  Ta thấy tương đương: a     move(3, a) = move(3, b) = move(4, a) = move(4, b) = b start a b  Ghép thành trạng thái start b TRƯƠNG XUÂN NAM a b a a a b a 32 Tối ưu DFA  Với DFA mới, ta thấy tương đương:     move(1, a) = move(1, b) = move(2, a) = move(2, b) = b start b b a a a  Ghép trạng thái thành trạng thái 1, ta trạng thái tối ưu sau b b start a a  Chú ý: chưa có thuật giải tối ưu cho toán TRƯƠNG XUÂN NAM 33 Tối ưu bảng chuyển  Tổ chức bảng chuyển thường sử dụng ma trận  Ưu điểm: đơn giản, dễ hiểu, tốc độ cao  Nhược điểm: kích thước lớn, dễ nhầm lẫn mã hóa  Có số chiến thuật tối ưu bảng chuyển, chủ yếu dựa ý tưởng nén trạng thái giống TRƯƠNG XUÂN NAM 34 Phần Bộ phân tích từ vựng dựa DFA TRƯƠNG XUÂN NAM 35 DFA thực tế DFA thực tế việc ghép từ nhiều DFA con, xem DFA từ loại mà đốn nhận TRƯƠNG XN NAM 36 Bộ PTTV dựa DFA // đầu vào: chuỗi x kết thúc kí hiệu EOF // đầu ra: trạng thái chấp nhận lỗi (ERROR) s := START; while (s != ERROR) { c := nextInput(x); if (c == EOF) break; s := move(s, c); } if (isAcceptState(s)) return acceptState(s); else return ERROR; TRƯƠNG XUÂN NAM 37 Phần Bài tập TRƯƠNG XUÂN NAM 38 Bài tập Hình bên thể đồ thị chuyển DFA (bắt đầu từ q0) Hãy cho biết DFA sau đốn nhận ngơn ngữ nào? (viết dạng biểu thức quy) DFA đoán nhận biểu thức nào? TRƯƠNG XUÂN NAM q0 q1 q2 1 q3 39 Bài tập DFA đoán nhận biểu thức quy nào? DFA đốn nhận biểu thức quy nào? DFA đốn nhận biểu thức quy nào? TRƯƠNG XN NAM 40 Bài tập Xây dựng NFA đoán nhận biểu thức (\+? | -?) d+ Xây dựng NFA đoán nhận biểu thức đây: (a* | b*)* (( | a) b)* (a | b)*abb(a | b)* (if | then | else) a((b|a∗c)x)∗|x∗a ab* (a|b)+ a (a|ε)b*ab Xây dựng DFA đoán nhận (0|(1(01*(00)*0)*1)*)* TRƯƠNG XUÂN NAM 41 Bài tập Chuyển đổi NFA sau thành DFA ε ε ε ε a ε ε b ε a b ε 10 Chuyển đổi NFA sau thành DFA TRƯƠNG XUÂN NAM 42 Bài tập 11 Chuyển đổi NFA sau thành DFA TRƯƠNG XUÂN NAM 43 Bài tập 12 Xây dựng DFA tối ưu cho: (a | b)*a(a | b) (a | b)*a(a | b)(a | b) (a | b)*a(a | b)(a | b)(a | b) 13 Tối ưu hóa DFA (nếu có thể) TRƯƠNG XUÂN NAM 44 Bài tập 14 Xây dựng DFA cho PTTV biểu thức Excel 10 Dấu “=” (bắt đầu biểu thức) Số nguyên dương Các phép toán: +, -, *, / Các cặp ngoặc Địa ô: A10, C6,… Số âm Số thực Lời gọi hàm: SUM, IF Địa tuyệt đối: $A$10, $C6,… Kiểu chuỗi (nằm cặp dấu nháy kép) TRƯƠNG XUÂN NAM 45 ...Nội dung Automat hữu hạn (FA) Đồ thị chuyển (transition diagram - TD) Automat hữu hạn không đơn định (NFA) Automat hữu hạn đơn định (DFA) Chuyển đổi từ biểu thức... tưởng xây dựng đoán nhận với lần thử TRƯƠNG XUÂN NAM Automat hữu hạn (FA)  Automat hữu hạn (finite-state automaton) dùng để đoán nhận lớp ngơn ngữ quy  Cấu trúc học FA gồm: Automat  Quá trình... thái (hoặc dừng báo lỗi) • Khơng chấp nhận kí hiệu đầu vào   Automat hữu hạn không đơn định (non-deterministic finite automata – NFA) • Chấp nhận kí hiệu đầu vào  • Với kí hiệu đầu vào, chuyển