0.3 Văn phạm phi ngữ cảnh  (Page 13/17)

A *G z3Az4 và A *G z2 trong đó | z3z2z4 |  2k = n.

Vậy A *G z3i z2 z4i , i  0.

Hiển nhiên chuỗi z = uz3z2z4y, với các chuỗi u, y nào đó.

Nếu đặt z3 = v, z2 = w và z4 = x, thì ta sẽ hoàn thành việc chứng minh.

Ứng dụng bổ đề bơm

Thí dụ 5.14 :Chứng minh L = {aibici | i  1} không phải là ngôn ngữ phi ngữ cảnh.

Chứng minh

Giả sử L là ngôn ngữ phi ngữ cảnh, khi đó có tồn tại số n (theo bổ đề bơm).

Xét chuỗi z = anbncn với | z |  n, ta có thể viết z = uvwxy thoả mãn bổ đề.

Ta thấy vx nằm trong anbncn và | vwx |  n, vậy vx không thể chứa cả ký hiệu a và ký hiệu c (do sau ký hiệu a bên phải nhất n+1 vị trí mới đến vị trí của c bên trái nhất). Nếu vx chỉ có chứa ký hiệu a, thì chuỗi uwy (trường hợp uviwxiy với i = 0) sẽ có chứa số ký hiệu b và c ít hơn số ký hiệu a vì | vx |  1. Vậy uwy không có dạng ajbjcj. Tương tự cho các trường hợp chuỗi vx chỉ chứa ký hiệu b hay c. Còn nếu trong vx có chứa ký hiệu a và b thì chuỗi uvy sẽ có chứa số ký hiệu c lớn hơn a và b, nên nó cũng không thể thuộc L. Cũng tương tự cho trường hợp vx chứa hai ký hiệu b và c. Cuối cùng, ta suy ra chuỗi uviwxiy  L, vì các ký hiệu a, b, c trong chúng không thể bằng nhau với mọi i. Mà theo giả thiết của bổ đề bơm, chuỗi này phải thuộc L, mâu thuẫn.

Vậy L không thể là CFL.

Thí dụ 5.15 :Chứng minh L = {aibjcidj | i, j  1} không phải là ngôn ngữ phi ngữ cảnh.

Chứng minh

Giả sử L là ngôn ngữ phi ngữ cảnh, khi đó có tồn tại số n (theo bổ đề bơm).

Xét chuỗi z = anbncndn với | z |  n, ta có thể viết z = uvwxy thoả mãn bổ đề.

Ta thấy vì vx nằm trong anbncndn và | vwx |  n, nên vx không thể chứa ít nhất hai ký hiệu khác nhau. Hơn nữa, nếu vx có chứa hai ký hiệu khác nhau, thì chúng phải là hai ký hiệu liên tiếp đứng cạnh nhau, chẳng hạn a và b. Nếu vx chỉ có chứa ký hiệu a, thì chuỗi uwy sẽ có số ký hiệu a ít hơn số ký hiệu c nên không thuộc L, mâu thuẫn. Tương tự với trường hợp chuỗi vx chỉ chứa ký hiệu b, c hoặc d. Bây giờ giả sử chuỗi vx có chứa a và b thì vwy vẫn có số ký hiệu a ít hơn c. Mâu thuẫn tương tự cũng xuất hiện khi chuỗi vx có chứa b và c hoặc c và d. Vì chỉ có thể có một trong các trường hợp này nên ta có thể kết luận rằng L không thể là CFL.

Câu hỏi :

?

Hãy so sánh các yếu tố ràng buộc trong phát biểu Bổ đề bơm cho ngôn ngữ phi ngữ cảnh và Bổ đề bơm cho ngôn ngữ chính quy ?

Tính chất đóng của cfl

ĐỊNH LÝ 5.7 : CFL đóng với phép hợp, phép nối kết và phép bao đóng Kleene.

Chứng minh

Đặt L1 và L2 là hai CFL sinh bởi các CFG G1 (V1, T1, P1, S1) và G2 (V2, T2, P2, S2).

Vì các biến có thể đổi tên mà không ảnh hưởng tới ngôn ngữ sinh ra nên ta có thể xem tập V1 và V2 là rời nhau. Ta cũng giả sử các biến mới S3, S4, S5  V1 hoặc V2

. Đối với L1  L2: Xây dựng văn phạm G3 (V1  V2  {S3}, T1  T2, P3, S3),

trong đó P3 = P1  P2  {S3  S1 | S2}.

Nếu w  L1 thì dẫn xuất S3 G3 S1 *G1 w là một dẫn xuất trong G3 (vì mỗi luật sinh trong G1 cũng là luật sinh trong G3). Tương tự mỗi chuỗi trong L2 có dẫn xuất trong G3 bắt đầu bằng S3  S2. Vậy L1  L2  L(G3).

Ngược lại, nếu w  L(G3) thì dẫn xuất S3 *G3 w phải bắt đầu bằng S3  S1 hoặc S3  S2. Tức là dẫn xuất có dạng S3 G3 S1 *G3 w hoặc S3 G3 S2 *G3 w. Trong trường hợp thứ nhất, do V1 và V2 rời nhau nên chỉ có các ký hiệu của G1 xuất hiện trong dẫn xuất S1 *G3 w. Vì trong các luật sinh của P3 chỉ có chứa các ký hiệu thuộc G1 và nằm trong tập luật sinh P1, nên ta có thể kết luận chỉ có những luật sinh thuộc P1 được dùng trong dẫn xuất S1 *G3 w. Vì thế S1 *G1 w và w  L1. Tương tự cho trường hợp dẫn xuất S3 G3 S2, ta cũng có w  L2. Vậy L(G3)  L1  L2, và vì thế L(G3) = L1  L2.