Các tính chất của ngôn ngữ phi ngữ cảnh
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.
18 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2391 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Các tính chất của ngôn ngữ phi ngữ cảnh, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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
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 269
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 270
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 271
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.
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.
S
a B
S
A
T1 T2
Trang 272
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)
u
v x
y
zA2
S
A1
Cây dẫn xuất T của w
Trang 273
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:
S uA1z (1)
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 274
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
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 (><).
Trang 275
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 276
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 277
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:
S uAz uvAyz uvxyz, (2)
với u, v, x, y, z ∈ T*.
*⇒ *⇒ *⇒
Trang 278
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
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 279
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 280
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 281
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 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.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 283
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 284
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 285
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.
Các file đính kèm theo tài liệu này:
- Các tính chất của NNPNC.pdf