tailieunhanh - Bài giảng Tin học lí thuyết: Chương 3 - Võ Huỳnh Trâm

Bài giảng "Tin học lí thuyết - Chương 3: Automata hữu hạn và biểu thức chính quy" cung cấp cho người học các kiến thức: Khái niệm DFA & NFA, sự tương đương giữa DFA & NFA, biểu thức chính quy, các tính chất của tập chính quy. . | Chương 3 Automata hữu hạn Biểu thức chính quy Nòi dung Khái niệm DFA NFA Sự tương đương giữa DFA NFA Biểu thức chính quy Các tính chất của tập chính quy Automata hữu hạn đơn định DFA 0 1 1 0 0 1 0 1 Bộ diều khiển o Trạng thái bắt đầu Trạng thái kết thúc Ví dụ x Phép chuyển trên nhãn x M Q z õ q0 F 1 Q tập hữu hạn các trạng thái p q. z bộ chữ cái nhập a b . w x y . ỗ hàm chuyển ánh xạ Q x z Q q0 e Q trạng thái bắt đầu. F G Q tập các trạng thái kết thúc. 3 Phân loại FA Mở rộng hàm chuyền trạng thái 1. õ q e q 2. õ q wa õ S q w a với V w a Ngôn ngữ điPơc chắp nhân L M x 5 q0 x c F 2 Ví du chuỗi nhập w 110101 QSinh w õ qo 1 q1 õ q0 11 õ q1 1 qo õ q0 110 õ q1 10 õ q0 0 q2 õ q0 1101 õ q1 101 õ q0 01 õ q2 1 q3 õ q0 11010 . õ q3 0 q1 õ q0 110101 . õ qn 1 q0 e F 4 Printed with FinePrint - purchase at Giải thuật hình thức Định nghĩa NFA Muc đích kiểm tra một chuỗi nhập X có thuộc ngôn ngữ L M được chấp nhận bởi automata M. Input chuỗi nhập x Output câu trả lời YES hoặc NO Giải thuât q q0 c nextchar c là ký hiệu nhập được đọc tiếp theo While c do begin q 5 q c c nextchar end If q in F then write YES else write NO M Q z õ q0 F Q tập hữu hạn các trạng thái. z bộ chữ cái nhập. ỗ hàm chuyển ánh xạ Q x z 2Q q0 e Q trạng thái bắt đầu. F G Q tập các trạng thái kết thúc. Chú ỷ khái niệm õ q a là tập hợp tất cả các trang thái p sao cho có phép chuyển từ trạng thái q trên nhãn a. Hàm chuyển trang thái mờ rông ỗ q e q S q wa p I có một trạng thái r trong ỗ q w mà pGỖ r a õ 5 q w a Õ P w oqeP õ q w với cQ 5 Automata hữu hạn không đơn định NFA Ví dụ về NFA Ví du cho automata M hình vẽ và xét chuỗi nhập 01001 Start Ví du xét chuỗi nhập w 01001 và NFA đã cho ở trên M q0 qn q2 q qj 0 1 5 q0 q2 q4 Nhận xét Ứng với một trạng thái và một ký tự nhập có thể có không môt hoặc nhiều phép chuyển trạng thái. DFA là một trường hợp đặc biệt của NFA Õ Input Trạng thái 0 1 q0 q0 q3 q1 0 q2 q2 q2 q2 q3 q4 0 q4 q4 q4 Do q4t F nên w 01001 G L M õ qo 0 qo q3 õ q0 01 õ õ qo 0 1 õ q0 q3