Bài giảng Chương trình dịch - Bài 4: Xây dựng DFA

Nội dung bài giảng tình bày: 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 chính 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 trên DFA. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch - Bài 4: Xây dựng DFA CHƯƠNG TRÌNH DỊCH BÀI 4: XÂY DỰNG DFA Nội dung 1. 2. 3. 4. 5. 6. 7. 8. 9. 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 chính 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 trên DFA Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Automat hữu hạn (FA) TRƯƠNG XUÂN NAM 3 Automat hữu hạn (FA)  Trong bài tập của phần trước, chúng ta đã xem xét một bộ PTTV đơn giản, một 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 nếu bổ sung các từ loại mới  Hoạt động chậm, mỗi từ loại được thử đoán nhận một lần; trường hợp tệ nhất (có lỗi) có độ phức tạp cao vì phải thử tất cả các từ loại  Trong phần này chúng ta sẽ thảo luận một thiết kế mới khắc phục vấn đề tốc độ dựa trên ý tưởng xây dựng bộ đoán nhận chỉ với một lần thử duy nhất TRƯƠNG XUÂN NAM 4 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ữ chính quy  Cấu trúc cơ học của 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 sẽ chuyển sang trạng thái nào Dừng khi kết thúc xâu vào và trả về trạng thái đoán nhận TRƯƠNG XUÂN NAM 5