TAILIEUCHUNG - ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY
ÔTÔMÁT HỮU HẠN (FA : Finite Automata) Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn trạng thái (states). Mỗi trạng thái của hệ thống tại mỗi thời điểm sẽ thay đổi tùy thuộc vào INPUT, Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA)., DFA có khả năng nhận dạng ngôn ngữ dễ dàng hơn NFA, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với ôtô mát hữu hạn không đơn định tương đương | ĐAI HỌC VINH KHOA CNTT Biên soạn: HOÀNG DANH LONG K50-CNTT Chương II ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY I. ÔTÔMÁT HỮU HẠN (FA : Finite Automata) Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn trạng thái (states). Mỗi trạng thái của hệ thống tại mỗi thời điểm sẽ thay đổi tùy thuộc vào INPUT Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). DFA có khả năng nhận dạng ngôn ngữ dễ dàng hơn NFA, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với ôtômát hữu hạn không đơn định tương đương. Ôtômát hữu hạn đơn định - DFA (Deterministic Finite Automata) Một cách hình thức ta định nghĩa ôtômát hữu hạn đơn định là bộ gồm năm thành phần (Q, , , q0, F), trong đó : Q là tập hợp hữu hạn các trạng thái. là bộ chữ cái hữu hạn. là hàm chuyển ánh xạ từ Q Q, tức là (q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a. q0 Q là trạng thái bắt đầu F Q là tập các trạng thái kết thúc Sơ đồ chuyển Một đồ thị có hướng, gọi là sơ đồ chuyển (transition diagram) tương ứng với một DFA như sau: Các đỉnh của đồ thị là các trạng thái của DFA; Nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a từ đỉnh q đến đỉnh p trong sơ đồ chuyển. Trạng thái khởi đầu q0 nhãn "Start".Các trạng thái kết thúc trong F được chỉ ra bằng hai vòng tròn. Minh họa DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển (q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu (q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận chuỗi được viết trên băng input phía trước đầu đọc, nhưng không bao gồm ký tự tại vị trí đầu đọc vừa dịch chuyển đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng và DFA chuyển đến trạng thái kết thúc, thì DFA mới chấp nhận toàn bộ chuỗi trên băng. Ngôn ngữ được chấp nhận bởi DFA Một chuỗi x được chấp nhận bởi ôtômát hữu hạn M (Q, , , q0, F) nếu (q0, .
đang nạp các trang xem trước
