Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ được biểu diễn bởi các biến được mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là ký hiệu kết thúc. Quy tắc quan hệ giữa các biến gọi là luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một chuỗi có thể gồm biến lẫn các ký hiệu kết thúc trong văn phạm.

Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là văn phạm G (V, T, P, S), trong đó :

. V là tập hữu hạn các biến (hay ký tự chưa kết thúc)

. T là tập hữu hạn các ký tự kết thúc, V  T = 

. P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A   với A là biến và  là chuỗi các ký hiệu  (V  T)*

. S là một biến đặc biệt gọi là ký hiệu bắt đầu văn phạm.

Thí dụ 5.1 : Văn phạm G ({S, A, B}, {a, b}, P, S ), trong đó P gồm các luật sinh sau:

S ® AB

A ® aA

A ® a

B ® bB

B ® b

Quy ước ký hiệu:

- Các chữ in hoa A, B, C, D, E, ... và S ký hiệu các biến (S thường được dùng làm ký hiệu bắt đầu ).

- Các chữ nhỏ a, b, c, d, e, ...; các chữ số và một số ký hiệu khác ký hiệu cho các ký hiệu kết thúc.

- Các chữ in hoa X, Y, Z là các ký hiệu có thể là ký hiệu kết thúc hoặc biến.

- Các chữ Hi-lạp , , , ... biểu diễn cho chuỗi các ký hiệu kết thúc và biến.

Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh của nó. Nếu A ® 1, A ® 2 , ... , A ® k là các luật sinh của biến A trong văn phạm nào đó, ta sẽ ghi ngắn gọn là A ® 1 | 2 | ... | k

Thí dụ 5.2 : Văn phạm trong Thí dụ 5.1 trên có thể viết gọn là :

S ® AB

A ® aA  a

B ® bB  b

Câu hỏi :

?

Bạn nghĩ gì về lớp ngôn ngữ có thể được sinh bởi văn phạm trong ví dụ trên ? Cơ chế nào có thể được sử dụng cho văn phạm để phát sinh ngôn ngữ ?

Dẫn xuất: Để định nghĩa ngôn ngữ sinh bởi văn phạm CFG G (V, T, P, S), ta dẫn nhập khái niệm dẫn xuất. Trước hết ta giới thiệu hai quan hệ G và *G giữa hai chuỗi trong tập (V  T)*. Nếu A   là một luật sinh trong văn phạm và ,  là hai chuỗi bất kỳ trong tập (V  T)* thì A G , hay ta còn nói luật sinh A   áp dụng vào chuỗi A để thu được chuỗi , nghĩa là A sinh trực tiếp  trong văn phạm G. Hai chuỗi gọi là quan hệ nhau bởi G nếu chuỗi thứ hai thu được từ chuỗi thứ nhất bằng cách áp dụng một luật sinh nào đó.

Giả sử 1, 2, ..., m là các chuỗi thuộc (V  T)* với m  1 và :

1 G 2, 2 G 3, …, m -1 G m

thì ta nói 1*G m hay 1 dẫn xuất ra m trong văn phạm G.

Như vậy, *G là bao đóng phản xạ và bắc cầu của G. Nói cách khác,  *G  nếu  được dẫn ra từ  bằng không hoặc nhiều hơn các luật sinh của P. Chú ý rằng  *G  với mọi chuỗi .

Thông thường nếu không có nhầm lẫn ta sẽ dùng các ký hiệu  và * thay cho ký hiệu G và *G. Nếu  dẫn ra  bằng i bước dẫn xuất thì ta ký hiệu  i .

Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh

Cho văn phạm CFG G(V, T, P, S), ta định nghĩa :

L(G) = {ww  T * và S *G w}

Nghĩa là, một chuỗi thuộc L(G) nếu:

1) Chuỗi gồm toàn ký hiệu kết thúc.

2) Chuỗi được dẫn ra từ ký hiệu bắt đầu S.

Ta gọi L là ngôn ngữ phi ngữ cảnh (CFL) nếu nó là L(G) với một CFG G nào đó. Chuỗi  gồm các ký hiệu kết thúc và các biến, được gọi là một dạng câu sinh từ G nếu S *. Hai văn phạm G1, G2 được gọi là tương đương nếu L(G1) = L(G2)

Thí dụ 5.3 : Xét văn phạm G (V, T, P, S), trong đó :

V = {S}, T = {a, b}, P = {S ® aSb, S ® ab}.

Bằng cách áp dụng luật sinh thứ nhất n -1 lần và luật sinh thứ hai 1 lần, ta có:

S Þ aSb Þ aaSbb Þ a3Sb3 Þ ... Þ an-1bn-1 Þ anbn

Vậy, L(G) chứa các chuỗi có dạng anbn, hay L(G) = {anbn  n  1}.

Để dễ hình dung sự phát sinh ra các chuỗi trong văn phạm phi ngữ cảnh, ta thường diễn tả một chuỗi dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa như sau:

Định nghĩa : Cho văn phạm G (V, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G được định nghĩa như sau :

i) Mỗi nút (đỉnh) có một nhãn, là một ký hiệu  (V  T  {})

ii) Nút gốc có nhãn là ký hiệu bắt đầu S.

iii) Nếu nút trung gian có nhãn A thì A  V

iv) Nếu nút n có nhãn A và các đỉnh n1, n2, ..., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì A  X1X2 ... Xk là một luật sinh trong tập luật sinh P.

v) Nếu nút n có nhãn là từ rỗng  thì n phải là nút lá và là nút con duy nhất của nút cha của nó.

Thí dụ 5.4 : Xét văn phạm G ({S, A}, {a, b}, P, S), trong đó P gồm:

S ® aAS | a

A ® SbA | SS | ba

Một cây dẫn xuất từ văn phạm có dạng như hình 5.1 sau :

Ta thấy, nút 1 có nhãn S và các con của nó lần lượt là a, A, S (chú ý S  aAS là một luật sinh). Tương tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A  SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S  a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A  ba).

Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi chuỗi này là chuỗi sinh bởi cây dẫn xuất.

Hình 1

Hình 5.1 - Cây dẫn xuất từ văn phạm

Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn được gọi là A-cây con (hoặc A-cây). Cây con cũng giống như cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký hiệu bắt đầu S.

Thí dụ 5.5 :Xét văn phạm và cây dẫn xuất trong Hình 5.1. Đọc các lá theo thứ tự từ trái sang phải ta có chuỗi aabbaa, trong trường hợp này tất cả các lá đều là ký hiệu kết thúc, nhưng nói chung cũng không bắt buộc như thế, lá có thể có nhãn là  hoặc biến. Ta thấy dẫn xuất S * aabbaa bằng chuỗi dẫn xuất :

S Þ aAS Þ aSbAS Þ aabAS Þ aabbaS Þ aabbaa

A-cây có nút đỉnh là 3 tạo ra chuỗi con abba theo chuỗi dẫn xuất :

S Þ SbAÞ abA Þ abba

Câu hỏi :

?

Các cây dẫn xuất được sinh từ những chuỗi dẫn xuất khác nhau cho cùng một chuỗi nhập có là những cây dẫn xuất khác nhau không ?

ĐỊNH LÝ 5.1 : Nếu G (V, T, P, S) là một văn phạm phi ngữ cảnh thì S *  nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra .

Nếu tại mỗi bước dẫn xuất, luật sinh được áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost) hay dẫn xuất trái. Tương tự, nếu biến bên phải nhất được thay thế ở mỗi bước dẫn xuất, đó là dẫn xuất phải nhất (rightmost) hay dẫn xuất phải. Nếu chuỗi w  L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tương ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất.

Thí dụ 5.7 : Xét cây dẫn xuất ở Hình 5.1

. Dẫn xuất trái nhất của cây :

S Þ aAS Þ aSbAS Þ aabAS Þ aabbaS Þ aabbaa.

. Dẫn xuất phải nhất tương ứng là :

S Þ aAS Þ aAa Þ aSbAa Þ aSbbaa Þ aabbaa.

Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w, thì G được gọi là văn phạm mơ hồ (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là mơ hồ nếu có một chuỗi w được dẫn ra từ ký hiệu bắt đầu S với hai dẫn xuất trái hoặc hai dẫn xuất phải.

Thí dụ 5.8 : Xét văn phạm G với các luật sinh như sau :

E  E + E  E * E  ( E )  a

Văn phạm này sinh ra các chuỗi biểu thức số học với 2 phép toán + và * . Với chuỗi a + a * a, ta có thể vẽ đến hai cây dẫn xuất khác nhau như sau :

Hình 5

(a) (b)

Hình 5.4 - Các cây dẫn xuất khác nhau cho cùng chuỗi nhập

Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau: thực hiện phép cộng trước hay phép nhân trước ? Để khắc phục sự mơ hồ này, ta có thể :

- Hoặc quy định rằng các phép cộng và nhân luôn luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G1 không mơ hồ tương đương như sau :

E  E + T  E * T  T

T  ( E )  a

- Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn được ưu tiên hơn phép cộng. Ta viết văn phạm G2 không mơ hồ tương đương như sau :

E  E + T  T

T  T * F  F

F  ( E )  a

Một ký hiệu X gọi là có ích nếu có một dẫn xuất S * X * w với các chuỗi ,  bất kỳ và w  T *. Ngược lại X gọi là vô ích.

Vậy, có 2 đặc điểm cho ký hiệu có ích:

- X phải dẫn ra một chuỗi ký hiệu kết thúc.

- X phải nằm trong dẫn xuất từ S.

Tuy nhiên 2 dấu hiệu trên không đủ để đảm bảo X có ích vì X có thể nằm trong dạng câu chứa một biến nhưng từ đó không có ký hiệu kết thúc được sinh ra.

BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)

Cho CFG G (V, T, P, S) với L(G)  , có một CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi A  V’ tồn tại w  T* để A * w.

Chứng minh

Mỗi biến A với luật sinh A  w trong P thì rõ ràng A  V’. Nếu A  X1X2 ... Xn là một luật sinh, trong đó mỗi Xi hoặc là ký hiệu kết thúc hoặc là một biến đã có sẵn trong V’ thì một chuỗi các ký hiệu kết thúc có thể được dẫn ra từ A bằng dẫn xuất bắt đầu A  X1X2 ... Xn, vì vậy A  V’. Tập V’ có thể tính được bằng cách lặp lại giải thuật trên. P’ là tập tất cả các luật sinh mà các ký hiệu của nó thuộc V’  T.

Giải thuật tìm V' như sau:

Begin

(1) OLDV:= Æ;

(2) NEWV:= {A  A  w với w  T *};

(3) While OLDV ¹ NEWV do

begin

(4) OLDV := NEWV;

(5) NEWV := OLDV  {A  A   với   (T  OLDV)*}

end;

(6) V' := NEWV;

end;

Rõ ràng rằng nếu biến A được thêm vào V’ tại bước (2) hoặc (5) thì A sẽ dẫn ra được chuỗi ký hiệu kết thúc. Ta chứng minh rằng nếu A dẫn ra được một chuỗi ký hiệu kết thúc thì A được thêm vào tập NEWV.

Dùng chứng minh quy nạp theo độ dài của dẫn xuất A * w.

Nếu độ dài bằng 1 thì A   là một luật sinh trong P. Vậy A được đưa vào V’ tại bước (2).

Giả sử kết quả đúng tới k -1 bước dẫn xuất ( k >1)

Nếu A  X1X2 ... Xn * w bằng k bước thì ta có thể viết w = w1w2 ... wn, trong đó Xi * wi, với 1  i  n bằng ít hơn k bước dẫn xuất. Theo giả thiết quy nạp thì các biến Xi này được thêm vào V’. Khi Xi cuối cùng được thêm vào V’ thì vòng lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ được thêm vào V’ tại (5).

Ta chứng minh L(G’) = L(G) :

Chọn V’ là tập hợp tại (6) và P' là tập tất cả các luật sinh mà các ký hiệu của nó thuộc (V’  T) thì chắc chắn rằng có tồn tại văn phạm G’ (V’, T, P’, S) thoả mãn tính chất: nếu A  V’ thì A * w với w nào đó thuộc T *. Hơn nữa, mỗi luật sinh của P’ đều là luật sinh của P nên ta có L(G’)  L(G).

Ngược lại giả sử một từ w  L(G) - L(G’) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc V – V’ hoặc luật sinh thuộc P – P’ (các dẫn xuất này đưa ra các biến thuộc V – V’), nhưng do không có biến nào trong V – V’ dẫn đến chuỗi kết thúc, điều này dẫn đến mâu thuẫn.

Vậy L(G’) = L(G).

Hay có thể nói 2 ngôn ngữ được cho từ 2 văn phạm G và G’ là tương đương nhau, hay nói cách khác: nếu có một văn phạm G thì luôn luôn có một văn phạm G’ tương ứng mà trong đó mỗi biến của G’ đều cho ra ký hiệu kết thúc.

BỔ ĐỀ 2: (Dùng loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu văn phạm)

Nếu G (V, T, P, S) là CFG thì ta có thể tìm được CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi X  V’  T’ tồn tại ,   (V’  T’)* để S * X.

Chứng minh

Tập V’  T’ gồm các ký hiệu xuất hiện trong dạng câu của G được xây dựng bởi giải thuật lặp như sau :

. Đặt V’ = {S}; T’ = ;

. Nếu A  V’ và A  1| 2 | ... | n là các luật sinh trong P thì thêm tất cả các biến của 1, 2, ... , n vào V’ và các ký hiệu kết thúc của 1, 2 ,..., n vào T’.

. Lặp lại giải thuật cho đến khi không còn biến hoặc ký hiệu kết thúc nào được thêm vào nữa.

Dễ thấy, X  V’  T’ thì tồn tại ,   (V’  T’)* để S * X, trong đó P’ là tập hợp tất cả các luật sinh của P chỉ chứa các ký hiệu thuộc (V’  T’).

Ta dễ dàng chứng minh L(G’) = L(G) .

ĐỊNH LÝ 5.2: Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng được sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký hiệu vô ích.

Chứng minh

Đặt L = L(G) là CFL không rỗng.

Đặt G1 là kết quả của việc áp dụng bổ đề 1 vào G và G2 là kết quả của việc áp dụng bổ đề 2 vào G1.

Giả sử G2 có ký hiệu vô ích là X. Theo bổ đề 2 ta có S *G2 X. Vì tất cả các ký hiệu trong G2 đều có trong G1 nên theo bổ đề 1: S *G1 X *G1 w với w là chuỗi ký hiệu kết thúc. Vì vậy không có ký hiệu nào trong dẫn xuất X *G1 w bị loại bỏ bởi bổ đề 2, vậy X dẫn ra ký hiệu kết thúc trong G2 . Suy ra X là ký hiệu có ích (mâu thuẫn).

Vậy văn phạm G2 không có ký hiệu vô ích nào.

Thí dụ 5.9 : Xét văn phạm có các luật sinh sau :

S ® AB | a

A ® a

Áp dụng bổ đề 1, ta thấy không có ký hiệu kết thúc được nào dẫn ra từ B nên ta loại bỏ B và luật sinh S  AB. Tiếp tục, áp dụng bổ đề 2 cho văn phạm :

S ® a

A ® a

Ta thấy chỉ có S xuất hiện trong dạng câu. Vậy ({S}, {a}, {S ® a}, S) là văn phạm tương đương với văn phạm đã cho và không có ký hiệu vô ích.

Câu hỏi :

?

Bạn hãy cho nhận xét về thứ tự áp dụng Bổ đề 1 và Bổ đề 2 trong quá trình loại bỏ các ký hiệu vô ích trong văn phạm ?

Một luật sinh có dạng A   gọi là luật sinh .

Ta xét đến việc loại bỏ các luật sinh này. Nếu   L(G) thì không thể loại được tất cả các luật sinh , nhưng nếu   L(G) thì có thể. Phương pháp loại bỏ dựa trên việc xác định liệu một biến A có dẫn xuất A *  hay không ? Nếu có, ta gọi A là biến rỗng (nullable). Ta có thể thay thế mỗi luật sinh B  X1X2 ... Xn bằng tất cả các luật sinh được định dạng bởi việc xóa bỏ tập hợp con các biến Xi rỗng, nhưng không bao gồm luật sinh B  , ngay cả khi tất cả các Xi đều là biến rỗng.

ĐỊNH LÝ 5.3 : Nếu L = L(G) với CFG G (V, T, P, S) thì L - {  } là L(G’) với CFG G’ không có ký hiệu vô ích và không có luật sinh .

Chứng minh

Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp như sau : Bắt đầu, nếu A   là một luật sinh thì A là biến rỗng. Kế tiếp, nếu B  , trong đó  gồm toàn các ký hiệu là các biến rỗng đã được tìm thấy trước đó thì B cũng là biến rỗng. Lặp lại cho đến khi không còn biến rỗng nào được tìm thấy nữa.

Tập luật sinh P’ được xây dựng như sau : Nếu A  X1X2 ... Xn là một luật sinh trong P thì ta thêm tất cả các luật sinh A  12 ... n vào P’ với điều kiện :

1) Nếu Xi không là biến rỗng thì i = Xi;

2) Nếu Xi là biến rỗng thì i là Xi hoặc ;

3) Không phải tất cả i đều bằng .

Đặt G’’ = (V, T, P’, S). Ta sẽ chứng minh rằng với mọi A  V và w  T *, A *G’’ w nếu và chỉ nếu w   và A *G w.

Nếu: Đặt A  iG w và w  , ta chứng minh quy nạp rằng A *G’’ w.

Nếu i = 1 ta có A  w là một luật sinh trong P, và vì w   nên luật sinh này cũng thuộc P’.

Giả sử kết quả đúng tới i - 1 (i >1)

Xét A G X1X2 ...Xn  i -1G w. Ta viết w = w1w2 ...wn sao cho j, Xj *wj.

Nếu wj   và Xj là biến thì theo giả thiết quy nạp, ta có Xj *G’’ wj (vì dẫn xuất Xj * wj có ít hơn i bước). Nếu wj =  thì Xj là biến rỗng, vậy A  12 ...n là một luật sinh trong P', trong đó j = Xj nếu wj   và j =  nếu wj = .

Vì w   nên không phải tất cả j là . Vậy, ta có dẫn xuất :

A Þ 12 ...n Þ* w12 ...n Þ* w1w23 ...n Þ* ... Þ* w1w2 ...wn = w trong G’’.

Chỉ nếu: Giả sử A  iG’’ w. Chắc chắn rằng w   vì G’’ không có luật sinh . Ta quy nạp theo i rằng A  G w.

Nếu i = 1: Ta thấy A  w là một luật sinh trong P’, do đó cũng phải có luật sinh A  w trong P sao cho bằng việc loại bỏ các ký hiệu rỗng trong , ta có w. Vậy, có tồn tại dẫn xuất A  G  Þ*G w, trong đó  Þ* w liên quan đến các dẫn xuất  từ các biến rỗng của  mà chúng ta đã loại bỏ khỏi w.

Giả sử kết quả đúng tới i - 1 (i >1)

Xét A G’’ X1X2 ... Xn  i - 1G’’ w. Phải có luật sinh A   trong P sao cho X1X2 ... Xn tìm được khi loại bỏ các biến rỗng của . Vậy A Þ*G X1X2 ...Xn (chứng minh tương tự như ở trên). Ta viết w = w1w2 ...wn sao cho j ta có Xj  *G’’ wj (bằng ít hơn i bước). Theo giả thiết quy nạp Xj  *G’’ wj nếu Xj là biến. Nếu Xj là ký hiệu kết thúc thì wj = Xj và Xj  *G wj là hiển nhiên. Vậy A  *G w.

Cuối cùng ta áp dụng bổ đề 2 vào G’’ ta thu được G’ không có ký hiệu vô ích. Vì bổ đề 1 và bổ đề 2 không đưa ra thêm luật sinh mới nào nên G’ không có chứa ký hiệu là biến rỗng hay ký hiệu vô ích.

Hơn nữa S  *G’ w nếu và chỉ nếu S  *G w. Vậy L(G’) = L(G) - {}.

Thí dụ 5.10 : Loại bỏ luật sinh e trong văn phạm sau :

S ® AB

A ® aA | e

B ® bB | e

Trước hết, ta xác định tập các biến rỗng trong văn phạm: A, B là các biến rỗng vì có các luật sinh A ® e và B ® e. S cũng là biến rỗng vì có luật sinh S ® AB với A, B đều là các biến rỗng.

 Tập biến rỗng Nullable = {A, B, S}

Theo quy tắc xây dựng tập luật sinh P’ trong định lý , ta có tập luật sinh mới như sau :

S ® AB | A | B

A ® aA | a

B ® bB | b

Lưu ý rằng văn phạm mới G’ không sản sinh ra , trong khi G lại có sinh ra từ rỗng e. Vậy muốn có một văn phạm thực sự tương đương với văn phạm G thì ta phải bổ sung thêm luật sinh S ® e vào tập luật sinh của G’. Ta có, văn phạm G’ tương đương G.

Một luật sinh có dạng A ® B với A, B đều là biến gọi là luật sinh đơn vị.

ĐỊNH LÝ 5.4 : Mỗi CFL không chứa e được sinh ra bởi CFG không có ký hiệu vô ích, luật sinh e hoặc luật sinh đơn vị .

Chứng minh

Đặt L là CFL không chứa e và L = L(G) với G (V, T, P, S) là một CFG nào đó.

Theo định lý 3 ta có thể giả sử G không có luật sinh e. Xây dựng tập hợp mới P’ gồm các luật sinh từ P như sau:

Đầu tiên đưa các luật sinh không là luật sinh đơn vị vào P’.

Sau đó, nếu có luật sinh đơn vị dạng A * B với A, B  V thì thêm vào P’ tất cả các luật sinh dạng A  , với B  không phải là luật sinh đơn vị của P.

Chú ý rằng ta có thể dễ dàng kiểm tra có hay không A  *G B vì G không có luật sinh e và nếu A  G B1  G B2 ...  G Bm  G B (trong đó một vài biến nào đó có thể xuất hiện 2 lần) thì ta có thể tìm một chuỗi rút ngắn hơn A  *G B, vì vậy ta chỉ xét các luật sinh đơn vị không có biến lặp lại.

Bây giờ ta sửa lại văn phạm G’ (V, T, P’, S). Chắc chắn rằng nếu A   là một luật sinh trong P’ thì A  *G . Vậy nếu có dẫn xuất trong G’ thì có dẫn xuất trong G. Giả sử rằng w  L(G). Xét dẫn xuất trái của w trong G:

S  G 0  G 1  G ...  G n = w.

Nếu 0  i < n thì nếu trong G có i  G i+1 bằng luật sinh không là luật sinh đơn vị thì trong G’ cũng có i  G’ i+1 không là luật sinh đơn vị. Giả sử i  G i+1 bằng luật sinh đơn vị, nhưng bước dẫn xuất trước đó i - 1  i không phải bằng luật sinh đơn vị hoặc i = 0. Và chuỗi dẫn xuất trong G từ i + 1  G i + 2  G ...  G j tất cả đều bằng luật sinh đơn vị, còn từ j  G j+1 không là luật sinh đơn vị thì ta thấy tất cả các i, i+1, …, j sẽ có cùng độ dài và vì chuỗi dẫn xuất là dẫn xuất trái nên các ký hiệu thay thế phải ở cùng một vị trí. Do vậy, tại vị trí này j  G j+1 bằng một luật sinh nào đó thuộc P’- P hay có nghĩa là một luật sinh không thuộc văn phạm G. Điều này sinh ra mâu thuẫn. Vậy L(G) = L(G’).

Ta còn có G’ không có chứa luật sinh đơn vị (theo chứng minh trên) nên G cũng sẽ không chứa luật sinh đơn vị (do G  G’).

Việc áp dụng bổ đề 1, bổ đề 2 để loại các ký hiệu vô ích không đưa ra thêm luật sinh nào chứng tỏ G không chứa ký hiệu vô ích.

Vậy, kết quả ta được một văn phạm thỏa điều kiện định lý.

Thí dụ 5.11 : Loại bỏ các luật sinh đơn vị trong văn phạm sau :

E ® E + T | T

T ® T * F | F

F ® ( E ) | a

Gọi tập A = {B  A  * B}, xét các biến trong văn phạm, ta có :

 E = { E, T, F } T = { T, F } F = { F }

Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau :

E ® E + T | T * F | ( E ) | a

T ® T * F | ( E ) | a

F ® ( E ) | a

ĐỊNH LÝ 5.5 : (Dạng chuẩn Chomsky, hay CNF )

Một ngôn ngữ phi ngữ cảnh bất kỳ không chứa  đều được sinh ra bằng một văn phạm nào đó mà các luật sinh có dạng A  BC hoặc A  a, với A, B, C là biến còn a là ký hiệu kết thúc.

Chứng minh

Đặt G là CFG sinh ra CFL không chứa . CFG tương đương có dạng chuẩn Chomsky có thể xây dựng từ G theo giải thuật sau :

Bước 1 : Thay thế tất cả các luật sinh có độ dài vế phải bằng 1 (luật sinh đơn vị dạng A  B, với A, B là biến )

Theo định lý 4.4, ta có thể tìm được CFG tương đương G1(V, T, P, S) không có luật sinh đơn vị và luật sinh . Vậy nếu luật sinh mà vế phải chỉ có một ký hiệu thì đó phải là ký hiệu kết thúc và luật sinh này là luật sinh có dạng đúng trong định lý.

Bước 2 : Thay thế các luật sinh có độ dài vế phải >1 và có chứa ký hiệu kết thúc.

Xét luật sinh trong P có dạng A  X1X2 ... Xm (m >1). Nếu Xi là ký hiệu kết thúc a thì ta đưa thêm một biến mới Ca và luật sinh mới Ca  a. Thay thế Xi bởi Ca, gọi tập các biến mới là V’ và tập luật sinh mới là P’.

Xét CFG G2 (V’, T, P’, S). Nếu   G1  thì  *G2 . Vậy L(G1)  L(G2). Ta chứng minh quy nạp theo số bước dẫn xuất rằng nếu A *G2 w, với A  V và w  T* thì A *G1 w.

Kết quả hiển nhiên với 1 bước dẫn xuất.

Giả sử kết quả đúng tới k bước dẫn xuất.

Xét A *G2 w bằng k +1 bước dẫn xuất.

Bước đầu tiên có dạng A  B1B2 ... Bm (m > 1). Ta có thể viết w = w1w2 ...wm trong đó Bi *G2 wi, 1  i  m. Nếu Bi là ký hiệu kết thúc ai nào đó thì wi là ai. Theo cách xây dựng P’ ta có luật sinh A  X1X2 ... Xm của P trong đó Xi = Bi nếu Bi V và Xi = ai nếu Bi V’- V. Với Bi  V, ta đã biết rằng có dẫn xuất Bi *G1 wi bằng ít hơn k bước, do vậy theo giả thiết quy nạp Xi *G1 wi. Vậy A *G1 w.

Ta đã có kết quả là một CFL bất kỳ được sinh ra từ một CFG mà mỗi luật sinh có dạng A  a hoặc A  B1B2 ... Bm (m  2) với A, B1, ... ,Bm là các biến và a là ký hiệu kết thúc. Ta sửa G2 bằng cách thêm vào P’ một số luật sinh.

Bước 3 : Thay thế các luật sinh có độ dài vế phải > 2 ký hiệu chưa kết thúc.

Xét luật sinh trong P’có dạng A  B1B2 ... Bm (m > 2) . Ta thay bằng tập hợp các luật sinh : A  B1D1

D1 ® B2D2

...

Dm - 3 ® Bm - 2Dm - 2

Dm - 2 ® Bm - 1Bm

Đặt V’’ là tập các biến mới, P’’ là tập các luật sinh mới và văn phạm mới G3 (V’’, T, P’’, S). Ta có G3 chứa các luật sinh thoả mãn định lý.

Hơn nữa, nếu A *G2  thì A *G3 , vậy L(G2)  L(G3). Ngược lại cũng đúng tức là, L(G3)  L(G2). Chúng ta cũng đã có L(G2)  L(G1) và L(G1)  L(G2). Vậy G3 là văn phạm thoả mãn dạng chuẩn CNF.

Thí dụ 5.12 : Tìm văn phạm có dạng CNF tương đương văn phạm sau :

S ® A | ABA

A ® aA | a | B

B ® bB | b

Bước 1 : Thay thế các luật sinh có độ dài vế phải = 1 (luật sinh đơn vị)

Gọi tập A = {B  A  * B }, xét các biến trong văn phạm, ta có :

 S = { S, A, B }

 A = { A, B}

 B = { B }

Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau :

S ® aA | a | bB | b | ABA

A ® aA | a | bB | b

B ® bB | b

Bước 2 : Thay thế các luật sinh có độ dài vế phải > 1 và có chứa ký hiệu kết thúc.

Ta thấy, a và b đều xuất hiện ở vế phải một số luật sinh, do đó ta tạo thêm 2 biến mới Ca, Cb và 2 luật sinh mới Ca ® a và Cb ® b.

Văn phạm tương đương có tập luật sinh như sau :

S ® CaA | a | CbB | b | ABA

A ® CaA | a | CbB | b

B ® CbB | b

Ca ® a

Cb ® b

Bước 3 : Thay thế các luật sinh có độ dài vế phải > 2

Chỉ còn duy nhất một luật sinh cần xét ở bước này : S ® ABA và tập luật sinh mới được thay thế có dạng như sau :

S ® CaA | a | CbB| b | AD1

A ® CaA | a | CbB| b

B ® CbB| b

Ca ® a

Cb ® b

D1 ® BA

Cuối cùng, ta sẽ thu được văn phạm có dạng chuẩn Chomsky như trên tương đương với văn phạm đã cho.

Ta gọi luật sinh với biến A ở bên trái là A - luật sinh.

BỔ ĐỀ 3 : (Dùng thay thế các luật sinh trực tiếp)

Cho G (V, T, P, S) là một CFG, đặt A ® 1B2 là luật sinh trong P và B ® 1 | 2 | ... | r là các B - luật sinh; văn phạm G1 (V, T, P1, S) thu được từ G bằng cách loại bỏ luật sinh A ® 1B2 và thêm vào luật sinh A ® 112 | 122 | ... | 1r2 thì L(G) = L(G1)

Chứng minh

. Hiển nhiên L(G1)  L(G) vì nếu A ® 1i2 được dùng trong dẫn xuất của G1 thì ta dùng A G 1B2 G 1i2

. Để chỉ ra L(G)  L(G1) ta cần chú ý rằng A ® 1B2 là luật sinh trong P - P1 (có trong G và không có trong G1). Bất cứ khi nào luật sinh A ® 1B2 được dùng trong dẫn xuất của G thì phải viết lại tại bước sau đó dùng luật sinh dạng B ® i. Hai bước dẫn xuất này có thể được thay thế bằng một bước dẫn xuất duy nhất, hay :

A ® 1B2A G1 1i2

B ® i

Vậy L(G) = L(G1)

BỔ ĐỀ 4 : (Dùng loại bỏ luật sinh dạng đệ quy trái trong văn phạm)

Đặt G (V, T, P, S) là CFG; A ® A1 | A2 | ... | Ar là tập các A - luật sinh có A là ký hiệu trái nhất của vế phải (luật sinh đệ quy trái). Đặt A ® 1 | 2 | ... | s là các A - luật sinh còn lại; G1 (V  {B}, T, P1, S) là CFG được tạo thành bằng cách thêm biến mới B vào V và thay các A - luật sinh bằng các luật sinh dạng:

1) A ® i

A ® i B với 1  i  s

2) B ® i

B ® i B với 1  i  r

thì L(G) = L(G1).

Chứng minh

Trong một chuỗi dẫn xuất trái, một chuỗi luật sinh dạng A ® Ai phải kết thúc bằng A ® j. Tức là:

A  Ai1  Ai2i1  ...  Aipip-1…i1  jipip-1…i1

Chuỗi dẫn xuất trong G có thể thay bằng chuỗi dẫn xuất trong G1 bởi :

A  j BÞ j ipB Þ jipip-1…B Þ ... Þ jipip-1…i2B

Þ jipip-1…i1.

Sự chuyển đổi ngược lại cũng có thể được.

Vậy L(G) = L(G1).

ĐỊNH LÝ 5.6 : (Dạng chuẩn Greibach, hay GNF )

Mỗi CFL bất kỳ không chứa  được sinh ra bởi một CFG mà mỗi luật sinh có dạng A  a với A là biến, a là một ký hiệu kết thúc, và  là một chuỗi các biến (có thể rỗng).

Chứng minh

Bước 1: Đặt G là CFG sinh ra CFL không chứa . Xây dựng văn phạm tương đương G’ có dạng chuẩn Chomsky.

Bước 2: Đổi tên các biến trong tập của G’ thành A1, A2, ..., Am (m  1) với A1 là ký hiệu bắt đầu. Đặt V = {A1, A2, ..., Am}.

Bước 3: Thay thế các luật sinh sao cho nếu Ai  Aj là một luật sinh thì j > i

Bắt đầu từ A1 và tiến tới Am, ta thay thế các Ak - luật sinh :

Nếu Ak  Aj là luật sinh với j < k: sinh ra một tập luật sinh mới bằng cách thay thế Aj bên vế phải của mỗi Aj - luật sinh theo bổ đề 3. Lặp lại không quá k - 1 lần ta thu được tập luật sinh dạng Ak  Al với l  k.

Sau đó, các luật sinh với l = k được thay thế theo bổ đề 4 bằng cách đưa vào các biến mới Bk.

Giải thuật cụ thể như sau:

Begin

(1) For k := 1 to m do begin

(2) for j := 1 to k-1 do

begin

(4) for Tất cả luật sinh Aj   do

(5) Thêm luật sinh Ak  ;

(6) Loại bỏ luật sinh Ak  Aj

end;

begin

(8) Thêm các luật sinh Bk   và Bk  Bk;

(9) Loại bỏ luật sinh Ak  Ak

end;

(10) for Mỗi luật sinh Ak   trong đó  không bắt đầu bằng Ak do

(11) Thêm luật sinh Ak  Bk

end;

end;

Bằng cách lặp lại bước xử lý trên cho mỗi biến nguồn, trong P chỉ chứa các luật sinh có dạng như sau :

1) Ai  Aj với j > i

2) Ai  ag với a Î T

3) Bk ® g g Î (V È {B1, B2 , ..., Bi - 1})*

Bước 4: Thay thế các Ai - luật sinh về đúng dạng.

Gọi V’ là tập biến mới phát sinh sau bước 3.

Chú ý rằng ký hiệu trái nhất của vế phải trong một luật sinh bất kỳ đối với biến Am phải là một ký hiệu kết thúc, vì Am là biến có chỉ số cao nhất. Ký hiệu trái nhất của vế phải của một Am-1- luật sinh bất kỳ phải là Am hoặc một ký hiệu kết thúc. Nếu là Am, ta tạo ra tập luật sinh mới bằng cách thay thế Am bởi chuỗi vế phải của các Am-luật sinh theo bổ đề 3. Tiếp tục quá trình này cho các luật sinh từ Am-2, ..., A2, A1 cho tới khi vế phải của tất cả các Ai - luật sinh có dạng bắt đầu bằng một ký hiệu kết thúc.

Bước 5: Thay thế các Bk -luật sinh về đúng dạng.

Bước cuối cùng, ta khảo sát các luật sinh với tập các biến mới B1, B2, ..., Bm.

Vì ta bắt đầu từ văn phạm đã có dạng chuẩn Chomsky, nên dễ dàng chứng minh quy nạp theo số lần áp dụng bổ đề 3 và bổ đề 4 rằng vế phải của mỗi Ai -luật sinh, với 1  i  n, bắt đầu bằng ký hiệu kết thúc hoặc AjAk với j, k nào đó. Vậy  (trong bước (7)) không khi nào có thể rỗng hoặc bắt đầu bằng một Bj khác, hay tất cả Bi - luật sinh đều có vế phải bắt đầu bằng ký hiệu kết thúc hoặc Ai. Một lần nữa, lại áp dụng bổ đề 3 cho mỗi Bi - luật sinh.

Ta thu được tập luật sinh trong văn phạm sau cùng thỏa đúng dạng chuẩn Greibach.

Thí dụ 5.13 : Tìm văn phạm có dạng GNF tương đương văn phạm G sau :

A1 ® A2A1 | A2A3

A2 ® A3A1 | a

A3 ® A2A2 | b

Bước 1 : G thỏa dạng chuẩn CNF sinh ra CFL không chứa 

Bước 2 : Ta có V = {A1, A2, ..., A3}

Bước 3 : Thay thế các luật sinh sao cho nếu Ai  Aj  là một luật sinh thì j > i.

Ta thấy trong tập luật sinh, các luật sinh cho A1 và A2 đã thỏa điều kiện j > i. Chỉ có luật sinh A3 ® A2A2 cần sửa đổi. Áp dụng bổ đề 3 để thay thế luật sinh này, ta có:A3 ® A3A1A2 | aA2

Sau đó, dùng bổ đề 4 để loại bỏ đệ quy trái, ta được tập luật sinh mới có dạng như sau :

A1 ® A2A1 | A2A3

A2 ® A3A1 | a

A3 ® aA2 | b | aA2B | bB

B ® A1A2 | A1A2 B

Bước 4 : Thay thế các Ai -luật sinh về đúng dạng.

Ở bước này, ta có thể thấy tất cả các A3 - luật sinh đã có dạng chuẩn. Tiếp tục, áp dụng bổ đề 3 để thay thế các A3 - luật sinh vào A2, A1, thu được tập luật sinh mới như sau:

A1 ® aA2A1A1 | bA1A1 | aA2BA1A1 | bBA1A1 | aA1|

aA2A1A3 | bA1A3 | aA2BA1A3 | bBA1A3 | aA3

A2 ® aA2A1 | bA1 | aA2BA1| bBA1| a

A3 ® aA2 | b | aA2B | bB

B ® A1A2 | A1A2 B

Bước 5 : Thay thế các Bk - luật sinh về đúng dạng.

B ® aA2A1A1A2 | bA1A1A2 | aA2BA1A1A2 | bBA1A1A2 | aA1A2

| aA2A1A3A2 | bA1A3A2 | aA2BA1A3A2 | bBA1A3A2 | aA3A2

| aA2A1A1A2B | bA1A1A2B | aA2BA1A1A2B | bBA1A1A2B | aA1A2 B

| aA2A1A3A2B | bA1A3A2B | aA2BA1A3A2B | bBA1A3A2B | aA3A2B

Cuối cùng, ta thu được văn phạm có dạng GNF với 39 luật sinh.

(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 : uviwxiy Î 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.

Hình 6

z3 z2 z4

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 = 2k. Nếu z  L(G) và | z |  n thì | z | > 2k-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 v1 và v2 có cùng nhãn là A

2) Đỉnh v1 gần gốc hơn v2

3) Phần đường đi từ v1 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 T1 có đỉnh là v1 biểu diễn dẫn xuất của chuỗi con có độ dài không quá 2k (vì trong cây con T1 không có đường đi nào có độ dài vượt quá k+1). Đặt z1 là chuỗi sinh ra từ cây T1. Ta gọi T2 là một cây con có nút gốc là v2, rõ ràng T2 là cây con của T1. Giả sử T2 sinh ra chuỗi z2 thì ta có thể viết z1 = z3z2z4. Hơn nữa z3 và z4 không thể đồng thời bằng  vì luật sinh đầu tiên trong cây dẫn xuất của T1 là A  BC với biến B, C nào đó. Cây con T2 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 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 ?

ĐỊ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.

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

. Đối với L1L2 : Xây dựng văn phạm G4 (V1  V2  {S4}, T1  T2, P4, S4) ,

trong đó P4 = P1  P2  {S4  S1S2}.

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

. Đối với L1* : Xây dựng văn phạm G5 (V1  {S5}, T1, P5, S5),

trong đó P5 = P1  { S5  S1S5 | }.

Ta cũng dễ dàng chứng minh được L(G5) = (L(G1))*.

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

Chứng minh

Ta đã biết ngôn ngữ L1 = {aibici | i  1} không là CFL. Ta có thể chứng minh :

. L2 = {aibicj | i  1 và j  1} là CFL vì L2 được sinh bởi văn phạm :

S ® AB

A ® aAb | ab

B ® cB | c

. L3 = {aibjcj | i  1 và j  1} cũng là CFL vì L3 được sinh từ văn phạm :

S ® CD

C ® aC | a

D ® bDc | bc

Tuy nhiên L2  L3 = L1 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 L1, L2 là hai CFL bất kỳ, theo quy luật DeMorgan ta có L1L1 size 12{L rSub { size 8{1} } } {}  L2L2 size 12{L rSub { size 8{2} } } {} = L1¯L2¯¯L1¯L2¯¯ size 12{ {overline { matrix { {overline {L rSub { size 8{1} } }} {} # union {overline {L rSub { size 8{2} } }} {} } }} } {} nên L1  L2 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)

Câu hỏi :

?

Hãy so sánh các tính chất đóng của lớp ngôn ngữ phi ngữ cảnh với lớp ngôn ngữ chính quy ?

ĐỊNH LÝ 5.9 : Tồn tại giải thuật để xác định CFL là: rỗng, hữu hạn, vô hạn.

Chứng minh

Với văn phạm G (V, T, P, S) :

. Để kiểm tra L(G) có rỗng hay không, ta dùng bổ đề 5. 1: Rõ ràng L(G) không rỗng khi và chỉ khi S sinh ra một chuỗi ký hiệu kết thúc nào đó.

. Để kiểm tra L(G) hữu hạn hay vô hạn, ta dùng định lý 5. 5 để tìm văn phạm tương đương G’ (V’, T, P’, S) có dạng chuẩn CHOMSKY và không có ký hiệu vô ích sinh ra L(G) - {}. L(G) hữu hạn khi và chỉ khi L(G’) hữu hạn.

Để kiểm tra tính hữu hạn của CFG có dạng chuẩn CHOMSKY, ta chỉ cần vẽ đồ thị có hướng với mỗi đỉnh trên đồ thị là một biến thuộc văn phạm và cạnh từ A đến B nếu và chỉ nếu có luật sinh A  BC hoặc A  CB với biến C bất kỳ. Khi đó, ngôn ngữ sinh ra là hữu hạn nếu và chỉ nếu đồ thị không có chu trình. Vì :

Nếu đồ thị có chu trình, giả sử chu trình là A0, A1,... , An, A0 thì sẽ có chuỗi dẫn xuất: A0  1A11  2A22 ...  nAnn  n+1 A0n+1, trong đó i, i là chuỗi các biến và | ii | = i. Vì không có ký hiệu vô ích nên n+1* w và n+1* x với mọi chuỗi w, x là các chuỗi ký hiệu kết thúc và độ dài tổng cộng ít nhất bằng n+1. Vì n  0, nên w và x không thể đồng thời bằng .

Kế tiếp, cũng do văn phạm không có chứa ký hiệu vô ích nên ta có thể tìm được các chuỗi y, z sao cho S * yA0z và chuỗi ký hiệu kết thúc v sao cho A0 * v. Vậy i ta có :

S * yA0z * ywA0xz * yw2A0x2z * ... * ywiA0xiz * ywivwiz.

Vì | wx | > 0, nên chuỗi ywivwiz không thể bằng ywjvwjz nếu i  j. Vậy văn phạm sinh ngôn ngữ vô hạn.

Ngược lại, giả sử đồ thị không có chu trình. Ta gọi hạng của biến A là độ dài lớn nhất của đường đi bắt đầu từ A. Vì không có chu trình nên A sẽ có hạng hữu hạn. Nếu A  BC là một luật sinh thì hạng của B và C phải nhỏ hơn hạng của A. Ta chứng minh quy nạp theo r (hạng của A) rằng không có chuỗi ký hiệu kết thúc nào có độ dài lớn hơn 2r

Với r = 0: hạng của A bằng 0, vậy không có cạnh từ A. Do đó, tất cả các A - luật sinh đều có dạng A  a, hay A dẫn ra chuỗi có độ dài l = 20.

Xét r > 0: nếu ta dùng luật sinh A  a thì dẫn ra chuỗi chỉ có độ dài 1, nếu dùng luật sinh A  BC thì vì B, C có hạng í hơn hoặc bằng r -1 nên theo giả thiết quy nạp B, C dẫn ra chuỗi có độ dài ngắn hơn 2r -1 . Vậy BC không thể dẫn ra chuỗi có độ dài lớn hơn 2r. Giả sử S có hạng là r0 thì các chuỗi do S sinh ra có độ dài không quá 2r0 . Vì thế suy ra ngôn ngữ là hữu hạn.

Thí dụ 5.16 : Xét văn phạm G chứa các luật sinh sau :

S ® AB

A ® BC | a

B ® CC | b

C ® a

Ta thấy văn phạm G có các luật sinh đã thỏa dạng chuẩn Chomsky.

. Để kiểm tra tính rỗng của văn phạm, ta áp dụng Bổ đề 5.1 lên tập biến V để tìm tập biến mới mới V­1 chỉ chứa các biến có khả năng dẫn ra chuỗi ký hiệu kết thúc trong văn phạm :

Ta có : V­1 = { A, B, C, S } vì A ® a , B ® b, C ® a và S ® AB

Hay S  V­1 có nghĩa là S có thể sinh ra các chuỗi ký hiệu kết thúc. Vậy ngôn ngữ sinh bởi văn phạm G : L(G) không rỗng.

. Để kiểm tra tính hữu hạn của văn phạm, ta vẽ đồ thị có hướng tương ứng với các luật sinh trong văn phạm như sau :

Hình 7

Hình 5.6 - Đồ thị có hướng tương ứng

Rõ ràng, ta thấy đồ thị không có chu trình. Hạng của S, A, B, C lần lượt là 3, 2, 1 và 0. Chẳng hạn, một đường đi dài nhất từ S là S  A  B  C. Vậy văn phạm này là hữu hạn, nó sinh ra hữu hạn chuỗi và độ dài các chuỗi không lớn hơn 23 = 8.

Thực tế, chuỗi dài nhất dẫn xuất được từ S là :

S  AB  BCB  CCCB  CCCCC * aaaaa ,với độ dài chuỗi là 5.

Nếu ta thêm vào văn phạm một luật sinh mới : C  AB, thì đồ thị có hướng tương ứng lúc đó có dạng như sau :

Hình 8

Hình 5.7 - Đồ thị có hướng tương ứng văn phạm bổ sung

Đồ thị mới này có nhiều chu trình, chẳng hạn A  B  C  A. Vậy ta phải tìm được một dẫn xuất dạng A * 3A3 , cụ thể là A  BC  CCC  CABC, trong đó 3 = C và 3 = BC. Vì C * a và BC * ba nên A * aAba.

Mặt khác, S * Ab và A * a, suy ra : S * aia(ba)ib, i. Vậy ngôn ngữ sinh từ văn phạm mới là vô hạn.

ĐỊNH LÝ 5.10 : Tồn tại giải thuật để xác định với một CFL nào đó sinh ra từ CFG G(V, T, P, S) và một chuỗi x bất kỳ thì x có thuộc L(G) hay không ?

Chứng minh

Có một vài giải thuật được đề nghị cho bài toán thành viên này. Sau đây trình bày một giải thuật theo vòng lặp đơn giản, ta gọi là giải thuật CYK (Cocke-Younger-Kasami) với thời gian tỷ lệ với  x 3.

Giả sử văn phạm G (V, T, P, S) đã có dạng chuẩn Chomsky và  x  = n  1. Trước hết, ta phải xác định với mỗi i, j và mỗi biến A, phải chăng A * xij , trong đó xij là một chuỗi con của chuỗi x tính từ vị trí thứ i và có độ dài j.

Ta chứng minh quy nạp theo độ dài j :

B * xik và C * x i+ k, j - k

Vì cả k và j – k đều nhỏ hơn j, nên theo giả thiết quy nạp ta đã xác định được liệu hai chuỗi dẫn xuất này có tồn tại hay không ? Thế thì cũng có thể c]xác định được liệu A * xij hay không ?

Với cách thực hiện như thế, ta sẽ xác định được phải chăng S * x1n , nhưng x1n = x, vậy x  L(G) khi và chỉ khi S * x1n.

Sau đây trình bày giải thuật CYK theo giải thuật trên, trong đó Vij là tập hợp tất cả các biến A sao cho A * xij . Chú ý rằng ta có thể giả thiết 1  i  n – j + 1, bởi vì lúc đó chuỗi con xij với độ dài j mới thực sự tồn tại.

Bước (1) và (2) xử lý trường hợp j = i. Vì văn phạm G đã cho sẵn, cho nên bước (2) chiếm mộ thời gian cố định. Vậy các bước (1) và (2) chiếm thời gian O(n). các vòng lặp For ở các dòng (3) và (4) làm cho các bước từ (5) đến (7) lặp lại nhiều nhất là n2 lần (do i, j  n). Bước (5) mỗi lần thực hiện cũng chiếm một khoảng thời gian cố định. Vậy tổng thời gian để thực hiện bước (5) là O(n2). Vòng lặp For ở dòng (6) làm cho bước (7) lặp lại n lần hoặc ít hơn. Vì bước (7) cũng chiếm một thời gian cố định, nên các bước (6) và (7) gộp lại chiếm thời gian O(n). Vì các bước này được thực hiện O(n2), nên tổng thời gia thực hiện cho bước (7) là O(n3). Vậy thời gian thực hiện toàn bộ giải thuật là ở cấp O(n3).

Giải thuật CYK:

Begin

(1) For i := 1 to n do

(2)Vij := { A  A  a là một luật sinh và a là ký hiệu thứ i trong x }

(3) For j := 2to n do

(4)for i := 1 to n – j + 1 do

begin

(5)Vij := 0;

(6)for k := 1 to j - 1 do

(7) Vij := Vij  { A  A  BC là một luật sinh, B  Vik

và C  Vi+ k, j – k }

end;

End;

Thí dụ 5.17 : Cho văn phạm G có dạng chuẩn Chomsky chứa các luật sinh sau :

S ® AB | BC

A ® BA | a

B ® CC | b

C ® AB | a

Xét chuỗi nhập x = baaba.

Bảng các Vij cho ở hình 5.8 dưới đây. Dòng đầu tiên trong bảng được cho bởi các bước (1) và (2) trong giải thuật. Vì x11 = x41 = b nên V11 = V41 = {B} vì B là biến duy nhất dẫn xuất ra b, còn x21 = x31 = x51 = a, suy ra V21 = V31 = V51 = {A, C} vì A và C có các luật sinh với a bên vế phải.

Hình 5.8 – Bảng các Vij

Để tính Vij với j > i, ta phải thực hiện vòng lặp For ở bước (6) và (7). Ta phải đối chiếu Vik với Vi+ k, j – k với k = 1, 2, …, j - 1 để tìm biến D trong Vik và biến E trong Vi+ k, j – k sao cho DE là vế phải của một hay nhiều luật sinh. Các vế trái của những luật sinh đó được đưa vào trong Vij. Quá trình đối chiếu đó diễn ra bằng cách giảm dần giá trị cột i, đồng thời tăng dần lên theo đường chéo qua Vij về phía phải như các chiều mũi tên vẽ trong hình 5.9.

Hình 5.9 – Quá trình tính các Vij

Chẳng hạn, để tính V24, đầu tiên ta đối chiếu V21 = {A, C} với V33 = {B}. Ta có V21 V33 = {AB, CB}. Vì có các luật sinh S  AB và C  AB nên S và C được đưa vào V24. Tiếp đến ta lại xét V22 V42 = {A}{S, A} = {BS, BA}. Vì có luật sinh A  BA, vậy ta đưa thêm A vào V24. Cuối cùng ta xét V23 V51 = {B}{A, C} = {BA, BC} gặp lại các vế phải đã xét, vậy không thể thêm gì vào V24. Vậy V24 = {S, AC}.

Cuối cùng, vì S  V15 , vậy chuỗi baaba là thuộc ngôn ngữ sinh ra bởi văn phạm đã cho.

Tổng kết chương V: Việc mô tả ngôn ngữ phi ngữ cảnh bằng phương tiện văn phạm phi ngữ cảnh tỏ ra rất hữu hiệu, cũng tương tự như việc sử dụng văn phạm BNF trong định nghĩa các ngôn ngữ lập trình. Trong chương này, chúng ta đã khảo sát tương đối cặn kẽ các phương tiện mô tả ngôn ngữ của văn phạm CFG thông qua các giải thuật tối ưu biến, giản lược, quy chuẩn và các tính chất của lớp ngôn ngữ mà nó mô tả. Câu hỏi đặt ra tiếp theo là có hay không một lớp ôtômát tương ứng để nhận dạng lớp ngôn ngữ phi ngữ cảnh. Như chúng ta đã thấy, lớp ngôn ngữ phi ngữ cảnh thực sự chứa lớp ngôn ngữ chính quy trong đó, nên ôtômát hữu hạn không thể nhận biết tất cả ngôn ngữ phi ngữ cảnh. Một cách trực quan, ôtômát hữu hạn có bộ nhớ bị hạn chế nghiêm ngặt, trong khi việc nhận dạng CFL có thể yêu cầu phải lưu trữ một lượng thông tin khá lớn. Khả năng cho sự mở rộng này sẽ được chúng ta xét đến trong nội dung của chương tiếp theo.

BÀI TẬP CHƯƠNG V

a) S ® aS | Sb | aSb | c

b) S ® SS | a | b

c) S ® SaS | b

d) S ® aSS | b

e)S ® aA | bB| c

A ® Sa

B ® Sb

f)S ® AB

A ® Sc | a

B ® dB | b

g)S ® TT

T ® aTa | bTb | c

5.2. Hãy chỉ ra một văn phạm phi ngữ cảnh sinh ra tập hợp :

a) Tập hợp các chuỗi đọc xuôi đọc ngược như nhau trên bộ chữ cái  = {0,1}.

b) Tập hợp chuỗi các dấu ngoặc đúng trong biểu thức số học.

c) Tập hợp {aibicj  i, j  0}

d) Tập hợp {ambn  m, n > 0}

e) Tập hợp {aicaj  i  j  0}

f) Tập hợp {ajbjcidi  i, j  1}

5.3. Cho văn phạm G với các luật sinh sau :

S ® aB | bA

A ® a | aS | bAA

B ® b | bS | aBB

Với chuỗi aaabbabbba , hãy tìm:

a) Dẫn xuất trái nhất.

b) Dẫn xuất phải nhất.

c) Cây dẫn xuất.

d) Văn phạm này có là văn phạm mơ hồ không ?

5.4. Cho văn phạm G với các luật sinh sau :

E ® T | E + T | E - T

T ® F | T  F | T / F

F ® a | b | c | (E)

Hãy vẽ cây dẫn xuất sinh ra các chuỗi nhập sau :

a) a – (b  c / a)

b) a  (b - c)

c) (a + b) / c

5.5. Cho văn phạm : S ® aSbS | bSaS | 

a) Chứng tỏ văn phạm này là văn phạm mơ hồ .

b) Xây dựng dẫn xuất trái (phải) và cây dẫn xuất tương ứng cho chuỗi abab.

c) Văn phạm này sinh ra ngôn ngữ gì ?

5.6. Chứng tỏ văn phạm sau đây là mơ hồ :

S ® If b then S else S

S ® If b then S

S ® a

Trong đó a, b, if, then, else là các ký hiệu kết thúc và S là biến.

5.7. Chứng tỏ văn phạm sau đây là mơ hồ :

S ® aBS | aB | bAS | bA

A ® bAA | a

B ® aBB | b

Hãy đề nghị một văn phạm không mơ hồ tương đương ?

5.8. Tìm CFG không có chứa ký hiệu vô ích tương đương với văn phạm:

a)S ® A | a

A ® AB

B ® b

b)S ® AB | CA

A ® a

B ® BC | AB

C ® aB | b

5.9. Tìm văn phạm tương đương với văn phạm sau không có chứa ký hiệu vô ích, luật sinh  và luật sinh đơn vị :

a)S ® aSbS | bSaS | 

b) S ® A | B

A ® aB | bS | b

B ® AB | Ba

C ® AS | b

c) S ® ABC

A ® BB | 

B ® CC | a

C ® AA | b

d) S ® A | B

A ® C | D

B ® D | E

C ® S | a | 

D ® S | b

E ® S | c | 

5.10. Tìm văn phạm chỉ có chứa một luật sinh  duy nhất S ®  tương đương với văn phạm sau :

S ® AB

A ® SA | BB | bB

B ® b | aA | 

5.11. Biến đổi các văn phạm sau đây về dạng chuẩn CHOMSKY:

a)S ® bA | aB

A ® bAA | aS | a

B ® aBB | bS | b

b)S ® aAB | BA

A ® BBB| a

B ® AS| b

c)S ® adAda | aSa | aca

A ® bAb | bdSdb

d) S ® 0S1 | 01

e) S ® #S | [ S  S] | p | q

5.12. Biến đổi các văn phạm sau đây về dạng chuẩn GREIBACH:

a) G ( {S, A}, {0, 1}, P, S) với các luật sinh :

S ® AA | 0

A ® SS | 1

b) G ( {A1, A2, A3}, {a, b}, P, A1) với các luật sinh :

A1 ® A2A3

A2 ® A3A1 | b

A3 ® A1A2 | a

c) G ( {A1, A2, A3, A4}, {a, b}, P, A1) với các luật sinh :

A1 ® A2A3 | A3A4

A2 ® A3A2 | a

A3 ® A4A4 | b

A4 ® A2A3 | a

5.13. Chứng minh rằng các ngôn ngữ sau không phải là CFL:

a)L = {ai bj ck i < j < k }

b)L = {ai bj j = i2 }

c)L = {ai i là số nguyên tố }

d) L = {anbncndn  n  0}

BÀI TẬP LẬP TRÌNH

5.14. Viết chương trình loại bỏ các ký hiệu vô ích trong một CFG.

5.15. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn CHOMSKY (CNF).

5.16. Viết chương trình chuẩn hóa một CFG thành dạng chuẩn GREIBACH (GNF).