Bài giảng lý thuyết ôtômát và ngôn ngữ hình thức chương 8: Tổng quan kiến thức

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

(cid:132) Họ NNPNC chiếm một vị trí trung tâm trong hệ thống phân cấp

(cid:132) Một mặt, NNPNC bao gồm các họ ngôn ngữ quan trọng nhưng

các ngôn ngữ hình thức.

(cid:132) Mặt khác, có các họ ngôn ngữ khác rộng lớn hơn mà NNPNC

bị giới hạn chẳng hạn như các NNPNC và PNCĐĐ.

(cid:132) Để 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.

(cid:132) Như trong Chương 4, chúng ta xem xét tính đóng dưới nhiều

chỉ là một trường hợp đặc biệt.

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

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.

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

(cid:132) Định lý 8.1

(cid:132) 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 |vxy| ≤ m |vy| ≥ 1 uvixyiz ∈ L

(cid:132) Chứng minh

(cid:132) Xét ngôn ngữ L – {λ}. Đây là NNPNC ⇒ ∃ văn phạm có dạng

(8.1) với (8.2) và (8.3) sao cho (8.4) ∀ i = 0, 1, 2, ... (cid:132) Định lý này được gọi là bổ đề bơm cho NNPNC.

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

chuẩn Chomsky G chấp nhận nó.

Chứng minh

(cid:132) Bổ đề

(cid:132) Nếu cây dẫn xuất của một chuỗi w được sinh ra bởi một văn

(cid:132) Bổ đề này có thể chứng minh bằng qui nạp dựa trên h.

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.

S S

(cid:132) 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.

(cid:132) Theo bổ đề trên suy ra T phải có ít nhất một con đường đi từ

B T2 A T1

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

gốc tới lá có chiều dài ≥ k+1.

Chứng minh (tt)

(cid:132) 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. (cid:132) 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

A2 u z

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

v x

Chứng minh (tt)

(cid:132) Trong cây trên, gọi u, v, x, y, z là các chuỗi có tính chất sau:

*⇒ uA1z S *⇒ vA2y A1 *⇒ A2 x w = uvxyz.

(1) (2) (3)

(cid:132) 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.

(cid:132) Từ (1), (2), (3) chúng ta có:

Và

*⇒

*⇒ uvAyz hay uvixyiz ∈ L ∀ i = 0, 1, 2, . . . (cid:132) Đ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

S uAz uviAyiz uvixyiz

Ví dụ

(cid:132) Bổ đề bơm này được dùng để chứng minh một ngôn ngữ là

(cid:132) Ví dụ

(cid:132) Chứng minh ngôn ngữ L = {anbncn : n ≥ 0} là không PNC.

(cid:132) Chứng minh

(cid:132) Giả sử L là PNC ⇒ ∃ số nguyên dương m.

không PNC tương tự như ở Chương 4.

Chọn w = ambmcm ∈ L. ∃ một phân hoạch của w thành bộ 5

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

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 (><).

Bài tập

(cid:132) Ngôn ngữ nào sau đây PNC? Chứng minh.

(cid:132) L1 = {anbjck: k = jn} (cid:132) L2 = {anbjck: k > n, k > j} (cid:132) L3 = {anbjck: n < j, n ≤ k ≤ j} (cid:132) L5 = { anbjanbj: n ≥ 0, j ≥ 0} (cid:132) L4 = {w: na(w) < nb(w) < nc(w)} (cid:132) L6 = { anbjakbl: n + j ≤ k + l} (cid:132) L7 = { anbjakbl: n ≤ k, j ≤ l} (cid:132) 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

(cid:132) Định nghĩa 8.1

(cid:132) Một NNPNC L được gọi là tuyến tính nếu ∃ một VPPNC tuyến

(cid:132) Định lý 8.2

(cid:132) Cho L là một NN tuyến tính vô hạn, tồn tại một số nguyên

tính G sao cho L = L(G).

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

Chứng minh

(cid:132) Gọi G là văn phạm tuyến tính mà không chứa luật sinh-đơn vị

(cid:132) Gọi k = max {các chiều dài vế phải} ⇒ mỗi bước dẫn xuất

và luật sinh-λ.

(cid:132) Đặt |V|= n. Chọn m = 2 + n(k-1). Xét w bất kỳ ∈ L, |w|≥ m. (1)

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).

*⇒

(cid:132) 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: uAz

⇒ 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.

*⇒ với u, v, x, y, z ∈ T*.

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

uvxyz, uvAyz (2) S

Chứng minh (tt)

(cid:132) Xét dẫn xuất riêng phần 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.

(cid:132) Từ (2) cũng suy ra:

*⇒

uAz uvAyz

*⇒

*⇒ uAz ⇒ uvixyiz ∈ L ∀ i = 0, 1, 2, ...

(cid:132) Chứng minh hoàn tất.

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

S uviAyiz uvAyz uvixyiz

Ví dụ

(cid:132) Chứng minh ngôn ngữ L = {w: na(w) = nb(w)} là không tuyến

(cid:132) Giả sử L là tuyến tính. Chọn w = amb2mam.

tính. (cid:132) Chứng minh

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

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.

Bài tập

(cid:132) Ngôn ngữ nào sau đây PNC tuyến tính? Chứng minh.

(cid:132) L1 = {anbnambm: n, m ≥ 0} (cid:132) L2 = { w: na(w) ≥ nb(w)} (cid:132) L3 = {anbj: j ≤ n ≤ 2j - 1} (cid:132) L4 = L(G) với G được cho như sau:

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

E → T | E + T T → F | T * F F → I | (E) I → a | b | c

Tính đóng của NNPNC

(cid:132) Định lý 8.3

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

(cid:132) Chứng minh

(cid:132) 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)

(cid:132) Định lý 8.4

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

(cid:132) Chứng minh

(cid:132) Hai ngôn ngữ {anbncm: n, m ≥ 0} và {anbmcm: n, m ≥ 0} là phi

(cid:132) 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

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.

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

(cid:132) Định lý 8.5

(cid:132) 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.

(cid:132) Chứng minh

(cid:132) Cho M1 = (Q, Σ, Γ, δ1, q0, z, F1) là npda chấp nhận L1 và M2 =

(cid:132) Xây dựng một npda M’= (Q’, Σ, Γ, δ’, q’0, z, F’) mô phỏng

(P, Σ, δ2, p0, F2) là dfa chấp nhận L2.

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

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,