Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 3 - ThS. Nguyễn Thị Thùy Linh

Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 3 Văn phạm chính quy và ôtômát hữu hạn cung cấp cho người học những kiến thức như: Ôtômát hữu hạn đơn định - DFA; Ôtômát hữu hạn không đơn định - NFA; Sự tương đương của NFA và DFA; Mối liên quan giữa VPCQ và OH; OHD không xuất phát lại; Các tính chất đóng của ngôn ngữ chính quy; Định lý KLEENE; Biểu thức chính quy; Thuật toán Thampson.
Nội dung trích xuất từ tài liệu:
Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 3 - ThS. Nguyễn Thị Thùy Linh Nội dungChương 3: 1. Ôtômát hữu hạn đơn định - DFA. 2. Ôtômát hữu hạn không đơn định - NFA. VĂN PHẠM CHÍNH QUY 3. Sự tương đương của NFA và DFA VÀ 4. Mối liên quan giữa VPCQ và OH 5. OHD không xuất phát lại ÔTÔMÁT HỮU HẠN 6. Các tính chất đóng của ngôn ngữ chính quy. 7. Định lý KLEENE. 8. Biểu thức chính quy. 9. Thuật toán Thampson 2 Ôtômát hữu hạn đơn định – DFA (Deterministic Finite Automata) Input : w  * Mô tả phi hình thức: 0 1 1 0 0 1 1 1 1 Ôtômát hữu hạn như một “máy” đoán nhận chuỗi, nó Băng từ sức chứa vô hạn làm việc như sau:  Băng từ chia thành nhiều ô. Mỗi ô có khả năng lưu Output : Yes, w  L q Bộ điều khiển trữ một ký hiệu của chuỗi nhập (chuỗi cần được No, w  L đoán nhận w є *).  Tùy theo cấu hình hiện tại gồm (trạng thái hiện thời của bộ điều khiển và ký hiệu trên ô mà đầu đọc quan sát được), mà Ôtômát  Có một đầu đọc, ở mỗi thời điểm quan sát một ô trên chuyển sang trạng thái mới, đồng thời đầu đọc dịch chuyển băng từ. sang phải một ô.  Có một bộ điều khiển Q gồm tập hợp hữu hạn trạng thái; ở mỗi thời điểm có một trạng thái hiện hành gọi  Quy luật chuyển sang trạng thái mới, được cho bởi một hàm, gọi là hàm chuyển trạng thái : Q x   Q. là trạng thái nội. 3 4 1 Trong Q có phân biệt q0  Q, gọi là trạng thái đầu và một tập hợp F chứa các trạng thái kết thúc.  Định nghĩa hình thức: Một ôtômát hữu hạn đơn định (viết tắt là Ta nói ôtômát đoán nhận (hay thừa nhận) một chuỗi vào w  *, nếu xuất phát từ q0, đầu đọc nhìn vào ký hiệu bên trái ÔHĐ) là một hệ thống M = (, Q, , q0, F) trong đó: nhất của w, sau một số bước hữu hạn làm việc, nó đọc xong   là một bộ chữ cái hữu hạn, gọi là bộ chữ vào. chuỗi w và rơi vào một trong các trạng thái kết thúc.  Q là một tập hữu hạn các trạng thái,   Q = . Tập hợp mọi chuỗi (được đoán nhận bởi Ôtômát) hợp thành  : Q x   Q, được gọi là hàm chuyển. ngôn ngữ được đoán nhận bởi ôtômát đó. Do Q là hữu hạn và hàm chuyển  là hàm toàn phần và đơn  q0  Q là trạng thái đầu. trị, cho nên bước chuyển của Ôtômát được xác định một  F  Q là tập các trạng thái cuối. cách duy nhất. Chính vì vậy mà Ôtômát mô tả như trên được gọi là ôtômát hữu hạn đơn định. 5 6 Biểu diễn hàm chuyển trạng  Ví dụ 3.1: Xét Ôtômát hữu hạn đơn định M(,Q, ,q0,F). trong đó:  = {0, 1}  Có 3 cách biểu diễn hàm chuyển (hàm chuyển trạng thái): Q = {q0, q1, q2, q3}  Theo định nghĩa  (qi, ...