- BÀI 2: ÔTÔMAT HỮU HẠN. - Ôtômat hữu hạn. - Thiết kế Ôtômat hữu hạn. - Ngôn ngữ chính quy. - Toán tử chính quy. - Ôtômat hữu hạn (Finite State Machine - FSM hay Finite Automation). - Các máy tính hoặc bộ điều khiển nhỏ - Có số trạng thái hữu hạn và khá nhỏ. - Biểu diễn hình học của Ôtômat hữu hạn. - Trạng thái bắt đầu: Biểu thị bởi mũi tên chỉ vào nó. - Trạng thái kết thúc: Biểu thị bởi vòng tròn kép. - Tạo ra các chuỗi tương ứng với mô hình của FSM. - Nhận diện các chuỗi có thỏa mãn mô hình FSM hay không. - Ví dụ nhận diện các chuỗi sau:. - Làm thế nào để biểu diễn các chuỗi chấp thuận bằng 1 ngôn ngữ?. - Ôtômat hữu hạn ≡ bộ 5 (hay 5 chiều) M = (Q, Σ, δ, q 0 , F) Trong đó:. - Q: Tập trạng thái (hữu hạn. - Σ: Bộ chữ, tập hữu hạn các ký tự - δ: Hàm dịch chuyển. - δ: Q x Σ→ Q - q 0 : Trạng thái bắt đầu (q 0 ∈ Q). - F: Là tập các trạng thái kết thúc (F ⊆ Q). - Ví dụ Ôtômat hữu hạn. - Ngôn ngữ của máy M. - Nếu A là tập tất cả các xâu mà máy M chấp nhận → A là ngôn ngữ của máy M. - Máy M đoán nhận (recognizes) A. - Do một máy có thể chấp thuận vài xâu nhưng nó luôn đoán nhận chỉ một ngôn ngữ. - Nếu máy không chấp thuận một xâu nào thì nó vẫn đoán nhận một ngôn ngữ (Ngôn ngữ rỗng - Ø). - Làm thế nào để đoán nhận tất cả các chuỗi không chứa chuỗi 0011?. - Trước tiên, ta thử với bài toán đơn giản hơn: Làm thế nào để đoán nhận tất cả các chuỗi có chứa chuỗi con 0011?. - Thiết kế Ôtômat hữu hạn M 1. - Một máy trạng thái (FSM) chấp thuận 1 chuỗi nào đó - Một máy trạng thái (FSM) đoán nhận 1 ngôn ngữ. - Ngôn ngữ mà máy M 1 đoán nhận. - Tập các chuỗi được xây dựng từ các ký tự {0,1}*. - Bản chất ngôn ngữ: Tập → L(M 1. - FSM trên đoán nhận các chuỗi . - L = {w| w là các chuỗi 01,10 hoặc các chuỗi có 1 số 1 liền ngay sau ít nhất 1 số 0}. - Các chuỗi sau điều gì sẽ xảy ra?. - Cho Ôtômat hữu hạn: M = (Q, Σ, δ, q 0 , F) và w. - Định nghĩa: Một ngôn ngữ được gọi là ngôn ngữ chính quy nếu có một Ôtômat hữu hạn nào đó đoán nhận nó. - Ngôn ngữ nào thì không được coi là ngôn ngữ chính quy?. - Giả sử A, B là các ngôn ngữ. - Ta có các toán tử chính quy sau:. - Lớp các ngôn ngữ chính quy là đóng đối với toán tử hợp. - Nếu A 1 và A 2 là ngôn ngữ chính quy thì A 1 ∪ A 2 cũng là ngôn ngữ chính quy. - Giả sử M 1 đoán nhận A 1 , M 2 đoán nhận A 2. - Xây dựng M để đoán nhận A 1 ∪ A 2 → Chứng minh bằng việc xây dựng. - M 1 = (Q 1 ,Σ,δ 1 ,q 1 ,F 1 ) đoán nhận A 1. - M 2 = (Q 2 ,Σ,δ 2 ,q 2 ,F 2 ) đoán nhận A 2. - Xây dựng M = (Q,Σ,δ,q 0 ,F) đoán nhận A 1 ∪ A 2. - Lớp các ngôn ngữ chính quy là đóng đối với toán tử ghép tiếp. - Nếu A 1 và A 2 là ngôn ngữ chính quy thì A 1 ◦ A 2 cũng là ngôn ngữ chính quy. - Xây dựng M để đoán nhận A 1 ◦ A 2 → Phần đầu đoán nhận A 1 , phần sau đoán nhận A 2. - Tuy nhiên, ta không biết xâu mà M đoán nhận bị cắt ở đâu
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt