tailieunhanh - Chương 2 -Automat Hữu Hạn

Introductory Example Chúng ta hãy tạo ra một ngôn ngữ nhỏ gấn như ngôn ngữ Pascal Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. , ||l a|b| 0|1 , , , và là các biến a, b, , 0, 1, là những ký tự kết thúc | Automat Hữu Hạn Finite Automata Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of Industry Introductory Example Chúng ta hãy tạo ra một ngôn ngữ nhỏ gần như ngôn ngữ Pascal. Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. , || a|b| 0|1 , , , và là các biến a, b, , 0, 1, là những ký tự kết thúc Introductory Example Một dẫn xuất cho định danh x1 => => x => x => x1 => x1 Biểu diễn Automat Dùng đồ thị: Các nút là các trạng thái nội. Các cạnh là các chuyển dịch. Nhãn của các cạnh cho biết điều gì xảy ra. a 1 2 Introductory Example An automaton that accepts all legal Pascal identifiers: 1 2 3 Letter Digit Letter or Digit Letter or Digit "yes" "no" Deterministic Finite | Automat Hữu Hạn Finite Automata Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of Industry Introductory Example Chúng ta hãy tạo ra một ngôn ngữ nhỏ gần như ngôn ngữ Pascal. Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. , || a|b| 0|1 , , , và là các biến a, b, , 0, 1, là những ký tự kết thúc Introductory Example Một dẫn xuất cho định danh x1 => => x => x => x1 => x1 Biểu diễn Automat Dùng đồ thị: Các nút là các trạng thái nội. Các cạnh là các chuyển dịch. Nhãn của các cạnh cho biết điều gì xảy ra. a 1 2 Introductory Example An automaton that accepts all legal Pascal identifiers: 1 2 3 Letter Digit Letter or Digit Letter or Digit "yes" "no" Deterministic Finite Automata (DFA) Một accepter hữu hạn đơn định hay một DFA được định nghĩa bởi bộ năm: M = (Q, , , q0, F) Q: finite set of internal states : finite set of symbols - input alphabet : Q Q transition function q0 Q: initial state F Q: set of final states Operational Manner Control unit q0 Input file yes/no Tại thời điểm ban đầu, nó được giả định đang ở trong trạng thái bắt đầu q0, với cơ chế nhập đang ở tại ký hiệu bên trái nhất của chuỗi nhập vào. Trong mỗi lần di chuyển của automat, đầu đọc tiến về phía phải một ký hiệu. Khi gặp ký hiệu kết thúc chuỗi, chuỗi nhập được chấp nhận nếu như automat đang ở một trong những trạng thái kết thúc của nó. Ngược lại thì chuỗi bị từ chối. Transition Graphs M = (Q, , , q0, F) |Q| vertices (circles) Edge (qi, qj) labelled a for (qi, a) = qj Initial verticle q0 Final vertices (double circles) in F Example 1 M = ({q0, q1, q2}, {0, 1}, , q0, {q1}) (q0, 0) = q0 (q0, 1) = q1 (q1, 0) = q0 (q1, 1) = q2 (q2, 0) = q2 (q2, 1) = q1 q0