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

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

• Với j = i : ta có A * xij khi và chỉ khi A  xij là một luật sinh.
• Với j>i : ta có A * xij khi và chỉ khi có một luật sinh dạng A  BC và số k, 1  k<j sao cho B dẫn xuất ra k ký hiệu đầu tiên của xij và C dẫn xuất ra j – k ký hiệu cuối của xij. Có nghĩa là :

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