Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 4

Tài liệu tham khảo Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức trường đaị học Bách Khoa khoa Công nghệ thông tin - Chương 4 Các tính chất Ngôn ngữ chính qui,Vật lý học một cách tổng quát nhất đó là khoa học nghiên cứu về "vật chất" và "sự tương tác".Cụ thể thì Vật lý khoa học nghiên cứu về các quy luật vận động của tự nhiên, từ thang vi mô (các hạt cấu tạo nên vật chất) cho đến thang vĩ mô (các hành tinh, thiên hà và vũ trụ). Trong tiếng Anh, từ...
Nội dung trích xuất từ tài liệu:
Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 4 Chương 4 Các tính chất của ngôn ngữ chính qui NNCQ tổng quát là như thế nào? Có phải chăng mọi ngôn ngữ hình thức đều là chính qui? Khi chúng ta thực hiện các phép toán trên NNCQ thì kết quả sẽ như thế nào, có còn là một NNCQ không? Một ngôn ngữ nào đó có hữu hạn không? Có rỗng không? Làm thế nào để biết một ngôn ngữ đã cho có là chính qui không? Trang 130 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Chương 4 Các tính chất của ngôn ngữ chính qui 4.1 Tính đóng của ngôn ngữ chính qui. 4.2 Các câu hỏi cơ bản về ngôn ngữ chính qui.. 4.3 Nhận biết các ngôn ngữ không chính qui Trang 131 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNCQ Đóng dưới các phép toán tập hợp đơn giản. Định lý 4.1 Nếu L1 và L2 là các NNCQ, thì L1∪L2, L1∩L2 , L1L2, L và L1* cũng vậy. Chúng ta nói rằng họ NNCQ là đóng dưới các phép hội, giao, kết nối, bù và bao đóng-sao. Chứng minh Nếu L1, L2 là chính qui thì ∃ các BTCQ r1, r2 sao cho L1= L(r1), L2= L(r2). Theo định nghĩa r1 + r2, r1r2 và r1* là các BTCQ định nghĩa các ngôn ngữ L1∪L2, L1L2, và L1*. Vì vậy họ NNCQ là đóng đối với các phép toán này. Để CM tính đóng đối với phép bù, cho M = (Q, Σ, δ, q0, F) là ^ dfa chấp nhận L1, thì dfa M = (Q, Σ , δ, q0, Q - F) chấp nhận L . Trang 132 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Đóng dưới các phép toán tập hợp đơn giản Để CM tính đóng đối với phép giao ta có hai cách như sau. Cách thứ nhất Dựa vào qui tắc De Morgan ta có L1 I L2 = L1 I L2 = L1 U L2 Dựa vào tính đóng của phép bù và phép hội vừa được chứng minh ở trên ta suy ra tính đóng đối với phép giao. Cách thứ hai Ta sẽ xây dựng một dfa cho L1 ∩ L2. Cho M1 = (Q, Σ, δ1, q0, F1) và M2 = (P, Σ, δ2, p0, F2) là các dfa lần lượt chấp nhận L1, L2. ^ ^ ^ ^ Ta xây dựng dfa M = (Q , Σ, δ , ( q0 , p0 ), F ) chấp nhận L1 ∩ L2 bằng thủ tục intersection sau. Trang 133 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục: intersection Thủ tục: intersection Input: dfa M1 = (Q, Σ, δ1, q0, F1) và dfa M2 = (P, Σ, δ2, p0, F2) ^ ^ ^ ^ Output: dfa M = (Q , Σ, δ , ( q0 , p0 ), F ) ^ ^ Q = Q × P, tức là Q = {(qi, pj): trong đó qi ∈ Q còn pj ∈ P}. Các chuyển trạng thái được xây dựng như sau ^ δ ((qi, pj), a) = (qk, pl) nếu và chỉ nếu δ1(qi, a) = qk và δ2(pj, a) = pl ^ F = {(qi, pj): trong đó qi ∈ F1 còn pj ∈ F2} Trang 134 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Thủ tục: intersection (tt) Cách xây dựng trên mô phỏng lại quá trình xử lý của đồng thời ^ ^ hai dfa M1 và M2. Ngoài ra dựa vào định nghĩa của δ ta thấy M chỉ chấp nhận những chuỗi mà được đồng thời cả hai dfa M1 và ^ M2 chấp nhận. Vì vậy M chấp nhận L1 ∩ L2. Ví dụ Tìm dfa giao của L1={a2nbm: n, m ≥ 0} và L2={a3nb2m: n, m ≥ 0} q1 q1 p0 b a a a a b q0 p1 q0 p2 L1 q0 q2 a a a p2 p1 q1 p2 q1 p1 a a b a a b L1 ∩ L2 b L2 p3 p4 p0 q2 p3 q0 p0 q2 p4 b b b Trang 135 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin Đóng dưới các phép toán tập hợp đơn giản (tt) Định lý 4.2 Họ NNCQ là đóng dưới phép hiệu và nghịch đảo. Chứng minh ...