Bài giảng Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú

Các tính chất của ngôn ngữ chính quy là nội dung bài 4 thuộc "Bài giảng Lý thuyết tính toán" tập trung vào tính đóng của ngôn ngữ chính quy; các câu hỏi cơ bản về ngôn ngữ chính quy; nhận biết các ngôn ngữ không chính quy. Mời các bạn cùng tìm hiểu và tham khảo nội dung thông tin tài liệu.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 04. Các tính chất của Ngôn ngữ Chính quy Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper GV: Nguyễn Ngọc TúTIN331 Tu.NguyenNgoc@hoasen.edu.vnNội dung Tính đóng của ngôn ngữ chính qui. Các câu hỏi cơ bản về ngôn ngữ chính qui.. Nhận biết các ngôn ngữ không chính quiTính Chất Của Ngôn Ngữ Chính Qui L1 và L2 là chính qui. Có thể nói gì về L1∪L2, L1∩L2 , L1●L2 , ?1, L1* ?Định Lý 1 Nếu L1 và L2 là chính qui thì L1∪L2, L1∩L2 , L1●L2 , ?1, L1* cũng là chính qui. Họ các ngôn ngữ chính qui là đóng đối với các phép toán giao, hợp, kết nối, lấy phần bù và bao đóng-sao.Chứng Minh L1 = L(r1) . L2 = L(r2) L(r1 + r2) = L(r1)∪L(r2) L(r1 . r2) = L(r1)L(r2) L(r1*) = (L(r1))*Chứng Minh M = (Q,∑, σ, q0, F) chấp nhận L1. M = (Q, ∑, σ, q0, Q – F) chấp nhận ?1.Chứng Minh M1 = (Q, , 1, q0, F1) M2 = (P, , 2, p0, F2) a1 an q0 qf 1(qi, a) = qk a1 an p0 pf 2(pj, a) = pl 1((qi, pj), a) = (qk, pl)Chứng Minh Chứng minh khác: L1∩L2= L1∩L2=?1 ∪ ?2 Ví dụ: L1 = {abn | n  0} L2 = {anb | n  0} L1L2 = {ab}Định Lý 2 Họ các ngôn ngữ chính qui là đóng đối với các phép toán hiệu và nghịch đảo: L2 chính qui  L1- L2 cũng chính qui  L 1,  L chính qui  LR cũng chính qui Chứng minh ?Đồng Hình (Homomorphism) Giả sử ∑ và ϓ là các bảng chữ cái.  h: ∑ϓ được gọi là một phép đồng hình Ảnh đồng hình của một chuỗi: w = a1a2 ... an  h(w) = h(a1)h(a2) ... h(an) Nếu L là một ngôn ngữ trên ∑ thì ảnh đồng hình của nó (homomorphic image) được định nghĩa: h(L) = {h(w): w ∈ L}Ex. = {a, b} = {a, b, c}h(a) = ab .h(b) = bbch(aba) = abbbcabL = {aa, aba}  h(L) = {abab, abbbcab}Đồng Hình Nếu r là một biểu thức chính qui trên , thì ảnh đồng hình của nó là một biểu thức chính qui h(r) đạt được bằng cách áp dụng phép đồng hình đối với mỗi ký hiệu trên  của r. = {a, b},  = {b, c, d} h(a) = dbcc h(b) = bdc r = (a + b*)(aa)* h(r) = (dbcc + (bdc)*)(dbccdbcc)*Định lý 3 Họ các ngôn ngữ chính qui là đóng đối với phép đồng hình:  Nếu L chính qui thì h(L) cũng chính qui Chứng minh:  Giảsử r là biểu thức chính qui sao cho L(r) = L.  Cần chứng minh: h(L(r)) = L(h(r)).Thương Đúng (Right Quotient) Giả sử L1 và L2 là các ngôn ngữ trên cùng một bảng chữ cái. Thì thương đúng của L1 với L2 được định nghĩa là: L1/L2 = {x | xy ∈ L1 và y ∈ L2}Ex .L1 = {anbm | n  1, m  0}{ba}L2 = {bm | m  1}L1/L2 = {anbm | n  1, m  0}Ex .L1 = {anbm | n  1, m  0}{ba} a b a b q0 q1 q2 b a q3 q5 a a, b a, b q4Định Lý Họ các ngôn ngữ chính qui là đóng đối với phép thương đúng: Nếu L1 và L2 chính qui thì L1/L2 cùng chính qui.Chứng Minh M = (Q, , , q0, F)  L1 . M^ = (Q, , , q0, F^)  L1/L2. y  L2 ; *(qi, y)  F  qi và F^ Mi = (Q, , , qi, F) và L(Mi)  L2  .Ex. Tìm L1/L2 cho L1 = L(a*baa*), L2 = L(ab*). a a a a M1 b a L1/L2 b a q0 q1 q2 q0 q1 q2 b M2 a p0 p1