Otmat08

Chương 8 Các tính chất của NNPNC „

„

„

„

„

Họ NNPNC chiếm một vị trí trung tâm trong hệ thống phân cấp các ngôn ngữ hình thức. Một mặt, NNPNC bao gồm các họ ngôn ngữ quan trọng nhưng bị giới hạn chẳng hạn như các NNPNC và PNCĐĐ. Mặt khác, có các họ ngôn ngữ khác rộng lớn hơn mà NNPNC chỉ là một trường hợp đặc biệt. Để nghiên cứu mối quan hệ giữa các họ ngôn ngữ và trình bày những cái giống nhau và khác nhau của chúng, chúng ta nghiên cứu các tính chất đặc trưng của các họ khác nhau. Như trong Chương 4, chúng ta xem xét tính đóng dưới nhiều phép toán khác nhau, các giải thuật để xác định tính thành viên, và cuối cùng là bổ đề bơm. Trang 268 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chương 8 Các tính chất của NNPNC 8.1 Hai bổ đề bơm 8.2 Tính đóng và các giải thuật quyết định cho NNPNC

Trang 269 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bổ đề bơm cho NNPNC „

Định lý 8.1 „

„

„

Cho L là một NNPNC vô hạn, tồn tại một số nguyên dương m sao cho bất kỳ chuỗi w nào ∈ L với |w| ≥ m, w có thể được phân hoạch thành w = uvxyz (8.1) với |vxy| ≤ m (8.2) và |vy| ≥ 1 (8.3) sao cho uvixyiz ∈ L (8.4) ∀ i = 0, 1, 2, ... Định lý này được gọi là bổ đề bơm cho NNPNC.

Chứng minh „

Xét ngôn ngữ L – {λ}. Đây là NNPNC ⇒ ∃ văn phạm có dạng chuẩn Chomsky G chấp nhận nó. Trang 270 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh „

Bổ đề „

„

Nếu cây dẫn xuất của một chuỗi w được sinh ra bởi một văn phạm Chomsky mà có chiều dài mọi con đường đi từ gốc tới lá nhỏ hơn hay bằng h thì |w| ≤ 2h-1. Bổ đề này có thể chứng minh bằng qui nạp dựa trên h. S S A B T2 T1 Trở lại chứng minh của định lý. Giả sử G có k biến (|V| = k). Chọn m = 2k. Lấy w bất kỳ ∈ L sao cho |w| ≥ m. Xét cây dẫn xuất T của w. Theo bổ đề trên suy ra T phải có ít nhất một con đường đi từ gốc tới lá có chiều dài ≥ k+1. a

„

„

Trang 271 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh (tt) „

„

Xét một đường như vậy. Trên đường này có ≥ k+2 phần tử. Nếu không tính nốt lá là kí hiệu kết thúc thì có ≥ k+1 nốt là biến. Vì tập biến chỉ có k biến ⇒ ∃ hai nốt trùng vào một biến. Giả sử đó là biến A (hai lần xuất hiện kí hiệu là A1 và A2) Cây dẫn xuất T của w

S A1 A2

u

z y

v

x

Trang 272 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh (tt) „

„

„

„

Trong cây trên, gọi u, v, x, y, z là các chuỗi có tính chất sau: * uA z (1) S ⇒ 1 * A1 ⇒ vA2y (2) * x A2 ⇒ (3) Và w = uvxyz. vxy là kết quả của cây có gốc là A1 mà mọi con đường của cây này có chiều dài ≤ (k +1) ⇒ theo bổ đề trên |vxy|≤ 2k = m. Mặt khác vì văn phạm có dạng chuẩn Chomsky tức là không có luật sinh-đơn vị và luật sinh-λ nên từ (2) suy ra |vy|≥ 1. Từ (1), (2), (3) chúng ta có: * uvAyz ⇒ * uviAyiz ⇒ * uvixyiz * uAz ⇒ S⇒ hay uvixyiz ∈ L ∀ i = 0, 1, 2, . . . Điều này kết thúc chứng minh. Trang 273 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ „

„

Ví dụ „

„

Bổ đề bơm này được dùng để chứng minh một ngôn ngữ là không PNC tương tự như ở Chương 4. Chứng minh ngôn ngữ L = {anbncn : n ≥ 0} là không PNC.

Chứng minh „

Giả sử L là PNC ⇒ ∃ số nguyên dương m. Chọn w = ambmcm ∈ L. ∃ một phân hoạch của w thành bộ 5 w = uvxyz Vì |vxy| ≤ m nên vxy không chứa đồng thời cả 3 kí hiệu a, b, c. Chọn i = 2 ⇒ w2 = uv2xy2z sẽ chứa a, b, c với số lượng không bằng nhau ⇒ w2 ∉ L (><). Trang 274 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bài tập „

Ngôn ngữ nào sau đây PNC? Chứng minh. „ „ „ „ „ „ „ „

L1 = {anbjck: k = jn} L2 = {anbjck: k > n, k > j} L3 = {anbjck: n < j, n ≤ k ≤ j} L5 = { anbjanbj: n ≥ 0, j ≥ 0} L4 = {w: na(w) < nb(w) < nc(w)} L6 = { anbjakbl: n + j ≤ k + l} L7 = { anbjakbl: n ≤ k, j ≤ l} L8 = {anbncj: n ≤ j}

Trang 275 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bổ đề bơm cho ngôn ngữ tuyến tính „

Định nghĩa 8.1 „

„

Một NNPNC L được gọi là tuyến tính nếu ∃ một VPPNC tuyến tính G sao cho L = L(G).

Định lý 8.2 „

Cho L là một NN tuyến tính vô hạn, tồn tại một số nguyên dương m sao cho bất kỳ chuỗi w nào ∈ L với |w| ≥ m, w có thể được phân hoạch thành w = uvxyz với |uvyz| ≤ m (8.7) và |vy| ≥ 1 (8.8) sao cho uvixyiz ∈ L (8.9) ∀ i = 0, 1, 2, ... Trang 276 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh „

„

„

„

Gọi G là văn phạm tuyến tính mà không chứa luật sinh-đơn vị và luật sinh-λ. Gọi k = max {các chiều dài vế phải} ⇒ mỗi bước dẫn xuất chiều dài dạng câu tăng tối đa (k-1) kí hiệu ⇒ một chuỗi w dẫn xuất dài p bước thì |w| ≤ 1 + p(k-1) (1). Đặt |V|= n. Chọn m = 2 + n(k-1). Xét w bất kỳ ∈ L, |w|≥ m. (1) ⇒ dẫn xuất của w có ≥ (n+1) bước ⇒ dẫn xuất có ≥ (n+1) dạng câu mà không phải là câu. Chú ý mỗi dạng câu có đúng một biến. Xét (n+1) dạng câu đầu tiên của dẫn xuất trên ⇒ ∃ hai biến của hai dạng câu nào đó trùng nhau, giả sử là biến A. Như vậy dẫn xuất của w phải có dạng: * * * uvAyz ⇒ S⇒ uAz ⇒ uvxyz, (2) với u, v, x, y, z ∈ T*. Trang 277 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Chứng minh (tt) „

„

„

Xét dẫn xuất riêng phần * uAz ⇒ * uvAyz S⇒ vì A được lặp lại trong (n + 1) dạng câu đầu tiên nên dãy này có ≤ n bước dẫn xuất ⇒ |uvAyz|≤ 1 + n(k-1), ⇒ |uvyz|≤ n(k-1) < m. Mặt khác vì G không có luật sinh-đơn vị và luật sinh-λ nên ta có |vy|≥1. Từ (2) cũng suy ra: * * * uAz ⇒ * uvAyz ⇒ uvixyiz S⇒ uviAyiz ⇒ ⇒ uvixyiz ∈ L ∀ i = 0, 1, 2, ... Chứng minh hoàn tất.

Trang 278 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ „

„

Chứng minh ngôn ngữ L = {w: na(w) = nb(w)} là không tuyến tính.

Chứng minh „

Giả sử L là tuyến tính. Chọn w = amb2mam. Từ (8.7) ⇒ u, v, y, z phải chứa toàn a. Nếu bơm chuỗi này lên, chúng ta nhận được chuỗi am+kb2mam+l, với k ≥ 1 hoặc l ≥ 1, mà chuỗi này ∉ L (><) ⇒ L không phải là ngôn ngữ tuyến tính.

Trang 279 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bài tập „

Ngôn ngữ nào sau đây PNC tuyến tính? Chứng minh. „ „ „ „

L1 = {anbnambm: n, m ≥ 0} L2 = { w: na(w) ≥ nb(w)} L3 = {anbj: j ≤ n ≤ 2j - 1} L4 = L(G) với G được cho như sau: E→T|E+T T→F|T*F F → I | (E) I→a|b|c

Trang 280 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Tính đóng của NNPNC „

Định lý 8.3 „

„

Họ NNPNC là đóng dưới phép hội, kết nối, và bao đóng sao.

Chứng minh „

Giả sử G1 = (V1, T1, S1, P1), G2 = (V2, T2, S2, P2) là hai VPPNC. Văn phạm G3 = (V1 ∪ V2 ∪ {S3}, T1 ∪ T2, S3, P1 ∪ P2 ∪ {S3 → S1 | S2}) sẽ có L(G3) = L(G1) ∪ L(G2). Văn phạm G4 = (V1 ∪ V2 ∪ {S4}, T1 ∪ T2, S4, P1 ∪ P2 ∪ {S4 → S1S2}) sẽ có L(G4) = L(G1)L(G2). Văn phạm G5 = (V1 ∪ {S5}, T1, S5, P1 ∪ {S5 → S1S5 | λ}) sẽ có L(G5) = L(G1)*. Trang 281 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Tính đóng của NNPNC (tt) „

Định lý 8.4 „

„

Họ NNPNC không đóng dưới phép giao và bù.

Chứng minh „

„

Hai ngôn ngữ {anbncm: n, m ≥ 0} và {anbmcm: n, m ≥ 0} là phi ngữ cảnh, tuy nhiên giao của chúng là ngôn ngữ {anbncn: n ≥ 0} lại không phi ngữ cảnh, nên họ NNPNC không đóng dưới phép giao. Dựa vào luật Morgan suy ra họ NNPNC cũng không đóng dưới phép bù. Vì nếu đóng đối với phép bù thì dựa vào tính đóng đối với phép hội suy ra tính đóng dưới phép giao theo luật Morgan.

Trang 282 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Tính đóng của NNPNC (tt) „

Định lý 8.5 „

„

Cho L1 là một NNPNC và L2 là một NNCQ, thì L1 ∩ L2 là phi ngữ cảnh. Chúng ta nói rằng họ NNPNC là đóng dưới phép giao chính qui.

Chứng minh „

„

Cho M1 = (Q, Σ, Γ, δ1, q0, z, F1) là npda chấp nhận L1 và M2 = (P, Σ, δ2, p0, F2) là dfa chấp nhận L2. Xây dựng một npda M’= (Q’, Σ, Γ, δ’, q’0, z, F’) mô phỏng hoạt động song song của M1 và M2 Q’ = Q × P, q’0 = (q0, p0), F’ = F1 × F2, δ’((qk, pl), x) ∈ ((qi, pj), a, b), ⇔ (qk, x) ∈ δ1(qi, a, b), và δ2(pj, a) = pl, Trang 283 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Tính đóng của NNPNC (tt) „ „

„

Nếu a = λ, thì pj = pl. Bằng qui nạp chứng minh rằng δ’*((q0, p0), w, z) |-*M’ ((qr, ps), x), với qr ∈ F1 và ps ∈ F2 ⇔ δ1*(q0, w, z) |-*M1 (qr, x), còn δ2*(p0, w) = ps. Vì vậy L(M’) = L(M1) ∩ L(M2) (điều phải chứng minh)

Trang 284 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Một vài tính chất khả quyết định của NNPNC „

Định lý 8.6 „

„

Cho một VPPNC G = (V, T, S, P), thì tồn tại một giải thuật để quyết định L(G) có trống hay không.

Định lý 8.7 „

Cho một VPPNC G = (V, T, S, P), thì tồn tại một giải thuật để quyết định L(G) có vô hạn hay không.

Trang 285 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin