Bài giảng Lý thuyết tính toán - Bài 04. Các tính chất của Ngôn ngữ Chính quy

GV: Nguyễn Ngọc Tú [email protected] Bài 04. Các tính chất của Ngôn ngữ Chính quy LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) TIN331 Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper Nộ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 qui Tí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) 2(pj, a) = pl 1(qi, a) = qk 1((qi, pj), a) = (qk, pl) q0 qf a1 an p0 pf a1 an Chứng Minh  Chứng minh khác: L1∩L2= L1∩L2=𝐿1 ∪ 𝐿2  Ví dụ: L1 = {ab n | n  0} L2 = {a nb | 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:  L1, L2 chính qui  L1- L2 cũng chính qui  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) = bbc h(aba) = abbbcab L = {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 = {a nbm | n  1, m  0}{ba} L2 = {b m | m  1} L1/L2 = {a nbm | n  1, m  0} Ex . q0 q1 q2 b b b a q3 a a, b a q4 q5 a, b a L1 = {a nbm | n  1, m  0}{ba} Đị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 b q0 q1 q2 M1 a b p0 p1 M2 a a a b q0 q1 q2 L1/L2 Các câu hỏi cơ bản về NNCQ  Cho một ngôn ngữ L và một chuỗi w, chúng ta có thể xác định được w có phải là một phần tử của L hay không?  Đây là một câu hỏi thành viên (membership) và phương pháp để trả lời nó được gọi là giải thuật thành viên.  Một ngôn ngữ đã cho là hữu hạn hay vô hạn?  Hai ngôn ngữ nào đó có giống nhau không?  Có hay không một ngôn ngữ là tập con của một ngôn ngữ khác? Các câu hỏi cơ bản về NNCQ  Biểu diễn chuẩn (Standard representation)  Chúng ta nói rằng một NNCQ là được cho trong một dạng biểu diễn chuẩn nếu và chỉ nếu nó được mô tả bởi một trong ba dạng sau đây: một ôtômát hữu hạn, một BTCQ hoặc một VPCQ.  Chú ý từ một dạng biểu diễn chuẩn này luôn có thể xác định được các dạng biểu diễn chuẩn khác nhờ vào các định lý đã được CM trước đây. Các định lý  Định lý 4.5  Cho một biểu diễn chuẩn của một NNCQ L bất kỳ trên Σ và một chuỗi w bất kỳ ∈ Σ*, thì tồn tại giải thuật để xác định w có ∈ L hay không.  Chứng minh  Chúng ta biểu diễn ngôn ngữ bằng một DFA rồi kiểm tra xem w có được chấp nhận bởi DFA này không.  Định lý 4.6  Tồn tại giải thuật để xác định một NNCQ đã cho trong một dạng biểu diễn chuẩn có trống, hữu hạn, vô hạn hay không.  Chứng minh  Chúng ta biểu diễn ngôn ngữ bằng một DFA. Nếu tồn tại một con đường đi từ trạng thái khởi đầu đến một trạng thái kết thúc nào đó thì ngôn ngữ là khác trống.  Để xác định ngôn ngữ có vô hạn không, ta tìm tất cả các đỉnh mà có chu trình đi qua nó. Nếu có một đỉnh trong số này thuộc một con đường nào đó đi từ trạng thái khởi đầu đến một trạng thái kết thúc thì ngôn ngữ là vô hạn, ngược lại thì là hữu hạn.  Định lý 4.7  Cho các biểu diễn chuẩn của hai NNCQ L1 và L2, tồn tại giải thuật để xác định có hay không L1 = L2.  Chứng minh  Sử dụng L1 và L2 chúng ta xây dựng ngôn ngữ:  L3 = (L1 I L2)U(L1 I L2)  Theo lý thuyết tập hợp ta có L1 = L2 khi và chỉ khi L3 = ∅. Vậy thay vì kiểm tra L1 có bằng L2 không ta chuyển về kiểm tra L3 có bằng ∅ không. Bằng tính đóng L3 là chính qui, và chúng ta có thể tìm thấy dfa M mà chấp nhận L3. Thêm vào đó chúng ta đã có giải thuật trong Định lý 4.6 để xác định xem L3 có bằng trống không. Nếu L3 = ∅ thì L1 = L2, ngược lại thì không. Nhận biết các NN không CQ  Sử dụng nguyên lý chuồng chim bồ câu  Nếu chúng ta đặt n vật thể vào trong m hộp, và nếu n > m, thì ít nhất có một hộp chứa nhiều hơn một vật thể.  Ngôn ngữ L = {anbn : n ≥ 0} có chính qui không?  Câu trả lời là không, như chúng ta sẽ chứng tỏ bằng cách sử dụng phương pháp phản chứng sau.  Giả sử L là chính qui thì ∃ dfa M = (Q, {a,b}, δ, q0, F) nào đó. Xét δ*(q0, ai) với i = 0, 1, 2, 3, ... Vì có một số không giới hạn các i, nhưng chỉ có một số hữu hạn các trạng thái trong M, theo nguyên lý chuồng chim bồ câu thì phải có một trạng thái nào đó, chẳng hạn q, sao cho  δ*(q0, an) = q và δ*(q0, am) = q, với n ≠ m.  Nhưng vì M chấp nhận anbn nên ta có δ*(q, bn) = qf ∈ F. Kết hợp với ở trên ta suy ra  δ*(q0, ambn) = δ*(q, bn) = qf . Bổ đề bơm  Định lý 4.8  Cho L là một NNCQ vô hạn, thì tồn tại một số nguyên dương m nào đó sao cho ∀ w ∈ L và |w| ≥ m đều tồn tại một cách phân tích w thành bộ ba  w = xyz,  với |xy| ≤ m, và |y| ≥ 1, sao cho wi =xyiz ∈ L  Chứng minh  Nếu L là chính qui, thì ∃ một dfa chấp nhận nó. Lấy một dfa như thế có tập trạng thái Q = {q0, q1, q2, ... ,qn}. Chọn m = |Q| = n + 1.  Lấy một chuỗi w bất kỳ ∈ L và |w| = k ≥ m. Xét một dãy các trạng thái mà ôtômát đi qua khi xử lý chuỗi w, giả sử là q0, qi, qj, . . . .,qf  Vì |w| = k suy ra dãy này có k + 1 phần tử. Vì k + 1 > n + 1 nên có ít nhất một trạng thái phải được lặp lại, và sự lặp lại này nằm trong n + 2 phần tử đầu tiên của dãy. Vì vậy dãy trên phải có dạng  q0 , qi , qj , ... , qr , ... , qr , ... , qf  suy ra phải có các chuỗi con x, y, z của w sao cho  δ*(q0, x) = qr ,  δ*(qr, y) = qr ,  δ*(qr, z) = qf ,  với |xy| ≤ n + 1 = m, vì sự lặp lại trạng thái xảy ra trong n + 2 phần tử đầu tiên, và |y| ≥ 1. Từ điều này suy ra  δ*(qr, xz) = qf và δ*(qr, xy iz) = qf , Ex.  Chứng minh L = wwr  w  a, b *  là không chính qui.  Giả sử L chính qui, nên có m để w = ambm bmam  L với w  = 4m  m  được phân tích thành w = xyz sao cho xy  m, y  1.  Suy ra y = ak , k  1 nên xy0z = xz = am-kbm bmam  L. Mâu thuẫn với bổ đề bơm. Vậy L không chính qui. Tóm tắt họ NNCQ NNCQ DFA NFA BTCQ VPTT-P VPTT-T DFAmin hiệu, nghịch đảo, đồng hình, thương đúng w ∈ L ? L = ∅ ? L vô hạn ? L1 = L2 ? L chính qui ?