intTypePromotion=1

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

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:0

0
116
lượt xem
32
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo bài thuyết trình 'bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - chương 8', kỹ thuật - công nghệ, kĩ thuật viễn thông phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

Nội dung Text: Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 8

  1. 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
  2. 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
  3. 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
  4. 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 a 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. Trang 271 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
  5. 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
  6. 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: * (1) S ⇒ uA1z * A1 ⇒ vA2y (2) * A2 ⇒ x (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ó: * * * * S ⇒ uAz ⇒ uvAyz ⇒ uviAyiz ⇒ uvixyiz 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
  7. 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. Ví dụ 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 (>
  8. 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
  9. 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
  10. 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: * * * S ⇒ uAz ⇒ uvAyz ⇒ 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
  11. Chứng minh (tt) Xét dẫn xuất riêng phần * * S ⇒ uAz ⇒ uvAyz 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: * * * * S ⇒ uAz ⇒ uvAyz ⇒ uviAyiz ⇒ uvixyiz ⇒ 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
  12. 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 (>
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2