TÍNH CHẤT CỦA NGÔN NGỮ PHI NGỮ CẢNH

Bổ đề bơm đối với CFL

(Dùng chứng minh một ngôn ngữ không là ngôn ngữ phi ngữ cảnh)

Cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc vào L sao cho nếu z ∈ L và | z | ≥ n thì ta có thể viết z = uvwxy sao cho:

1) | vx | ³ 1

2) | vwx | ≤ n và

3) ∀ i ³ 0 : uv i wx i y Î L

Chứng minh

Đặt G là văn phạm có dạng chuẩn CHOMSKY sinh L - {ε}. Chú ý rằng nếu z ∈ L(G) và cây dẫn xuất không có đường đi dài hơn i thì chuỗi sinh ra từ văn phạm có độ dài không dài hơn 2 ^{i -1}.

z 3 z 2 z 4

z = u v w x y

Hình 5.5 - Các bước dẫn xuất trong chứng minh Bổ đề bơm

Giả sử G có k biến, ta đặt n = 2^k. Nếu z ∈ L(G) và | z | ≥ n thì | z | > 2^k-1, vậy có một đường đi nào đó trên cây dẫn xuất có độ dài lớn hơn hoặc bằng k+1. Như vậy đường đi đó sẽ có ít nhất k+2 đỉnh, hay có ít nhất k+1 biến trên đường đi (chỉ có nút lá mới có thể không là biến), suy ra phải có biến xuất hiện hai lần, hơn nữa ta phải có:

1) Có hai đỉnh v₁ và v₂ có cùng nhãn là A

2) Đỉnh v₁ gần gốc hơn v₂

3) Phần đường đi từ v₁ tới lá có độ dài nhiều nhất là k+1 (đi từ lá lên tới gốc theo đường đi, chỉ có lá mới có thể là ký hiệu kết thúc vì vậy trong k+2 đỉnh đầu tiên phải có ít nhất k+1 biến và phải có ít nhất hai biến trùng nhau)

Xét cây con T₁ có đỉnh là v₁ biểu diễn dẫn xuất của chuỗi con có độ dài không quá 2^k (vì trong cây con T₁ không có đường đi nào có độ dài vượt quá k+1). Đặt z₁ là chuỗi sinh ra từ cây T₁. Ta gọi T₂ là một cây con có nút gốc là v₂, rõ ràng T₂ là cây con của T₁. Giả sử T₂ sinh ra chuỗi z₂ thì ta có thể viết z₁ = z₃z₂z₄. Hơn nữa z₃ và z₄ không thể đồng thời bằng ε vì luật sinh đầu tiên trong cây dẫn xuất của T₁ là A → BC với biến B, C nào đó. Cây con T₂ phải thuộc vào cây con sinh bởi bút biến B hoặc cây con sinh bởi nút biến C. Ta có :

A ⇒^*_G z₃Az₄ và A ⇒^*_G z₂ trong đó | z₃z₂z₄ | ≤ 2^k = n.

Vậy A ⇒^*_G z₃ⁱ z₂ z₄ⁱ , ∀i ≥ 0.

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

Nếu đặt z₃ = v, z₂ = w và z₄ = 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 = {aⁱbⁱcⁱ | 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 = aⁿbⁿcⁿ với | z | ≥ n, ta có thể viết z = uvwxy thoả mãn bổ đề.

Ta thấy vx nằm trong aⁿbⁿcⁿ 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 uvⁱwxⁱy 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 a^jb^jc^j. 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 uvⁱwxⁱy ∉ 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 = {aⁱb^jcⁱd^j | 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 = aⁿbⁿcⁿdⁿ với | z | ≥ n, ta có thể viết z = uvwxy thoả mãn bổ đề.

Ta thấy vì vx nằm trong aⁿbⁿcⁿdⁿ 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.

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 L₁ và L₂ là hai CFL sinh bởi các CFG G₁ (V₁, T₁, P₁, S₁) và G₂ (V₂, T₂, P₂, S₂).

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 V₁ và V₂ là rời nhau. Ta cũng giả sử các biến mới S₃, S₄, S₅ ∉ V₁ hoặc V₂

. Đối với L₁  L₂: Xây dựng văn phạm G₃ (V₁$$ V₂$${S3}, T₁$$ T₂, P₃, S₃),

trong đó P₃ = P₁  P₂  {S₃ → S₁ | S₂}.

Nếu w ∈ L 1 thì dẫn xuất S 3 ⇒ G3 S 1 ⇒ * G1 w là một dẫn xuất trong G 3 (vì mỗi luật sinh trong G 1 cũng là luật sinh trong G 3 ). Tương tự mỗi chuỗi trong L 2 có dẫn xuất trong G 3 bắt đầu bằng S 3 ⇒ S 2 . Vậy L 1  L 2 ⊆ L(G 3 ).

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.

Vậy ta đã chứng minh xong L(G3) = L1 L2, hay L1 L2 là CFL.

. Đối với L₁L₂ : Xây dựng văn phạm G₄ (V₁  V₂  {S₄}, T₁  T₂, P₄, S₄) ,

trong đó P₄ = P₁  P₂  {S₄ → S₁S₂}.

Chứng minh tương tự như trên ta có L(G 4 ) = L 1 L 2 , vậy L 1 L 2 cũng là CFL.

. Đối với L₁^* : Xây dựng văn phạm G₅ (V₁  {S₅}, T₁, P₅, S₅),

trong đó P₅ = P₁  { S₅ → S₁S₅ | ε}.

Ta cũng dễ dàng chứng minh được L(G 5 ) = (L(G 1 )) * .

ĐỊNH LÝ 5.8 : CFL không đóng với phép giao

Chứng minh

Ta đã biết ngôn ngữ L₁ = {aⁱbⁱcⁱ | i ≥ 1} không là CFL. Ta có thể chứng minh :

. L₂ = {aⁱbⁱc^j | i ≥ 1 và j ≥ 1} là CFL vì L₂ được sinh bởi văn phạm :

S ® AB

A ® aAb | ab

B ® cB | c

. L₃ = {aⁱb^jc^j | i ≥ 1 và j ≥ 1} cũng là CFL vì L₃ được sinh từ văn phạm :

S ® CD

C ® aC | a

D ® bDc | bc

Tuy nhiên L₂  L₃ = L₁ không phải là CFL.

Vậy CFL không đóng với phép giao.

Hệ quả : CFL không đóng với phép lấy phần bù.

Chứng minh

Giả sử CFL đóng với phép lấy phần bù, vậy với L₁, L₂ là hai CFL bất kỳ, theo quy luật DeMorgan ta có $L_1$  $L_2$ = $\overline{\begin{array}{cc}\overline{L_1}& \overline{L_2}\end{array}}$ nên L₁  L₂ là CFL hay CFL cũng đóng với phép giao. ( Điều này mâu thuẫn với định lý 6.6)