Các giả thuật quyết đinh CFL

Giải thuật xác định ngôn ngữ phi ngữ cảnh

ĐỊ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à A₀, A₁,... , A_n, A₀ thì sẽ có chuỗi dẫn xuất: A₀ ⇒ α₁A₁β₁ ⇒ α₂A₂β₂ ... ⇒ α_nA_nβ_n ⇒ α_n+1 A₀β_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 ⇒^* yA₀z và chuỗi ký hiệu kết thúc v sao cho A₀ ⇒^* v. Vậy ∀i ta có :

S ⇒^* yA₀z ⇒^* ywA₀xz ⇒^* yw²A₀x²z ⇒^* ... ⇒^* ywⁱA₀xⁱz ⇒^* ywⁱvwⁱz.

Vì | wx | > 0, nên chuỗi ywⁱvwⁱz không thể bằng yw^jvw^jz 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 2^r

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 = 2⁰.

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 2^{r -1} . Vậy BC không thể dẫn ra chuỗi có độ dài lớn hơn 2^r. Giả sử S có hạng là r₀ thì các chuỗi do S sinh ra có độ dài không quá 2^r0 . 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­₁ 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­₁ = { A, B, C, S } vì A ® a , B ® b, C ® a và S ® AB

Hay S ∈ V­₁ 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 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 2³ = 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 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 ⇒^* α₃Aβ₃ , cụ thể là A ⇒ BC ⇒ CCC ⇒ CABC, trong đó α₃ = C và β₃ = BC. Vì C ⇒^* a và BC ⇒^* ba nên A ⇒^* aAba.

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

Giải thuật thành viên (Membership)

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

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 ⇒^* x_ij , trong đó x_ij 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 :

• Với j = i : ta có A ⇒^* x_ij khi và chỉ khi A → x_ij là một luật sinh.
• Với j > i : ta có A ⇒^* x_ij 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 x_ij và C dẫn xuất ra j – k ký hiệu cuối của x_ij. Có nghĩa là :

B ⇒^* x_ik 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 ⇒^* x_ij hay không ?

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

Sau đây trình bày giải thuật CYK theo giải thuật trên, trong đó V_ij là tập hợp tất cả các biến A sao cho A ⇒^* x_ij . Chú ý rằng ta có thể giả thiết 1 ≤ i ≤ n – j + 1, bởi vì lúc đó chuỗi con x_ij 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à n² 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(n²). 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(n²), nên tổng thời gia thực hiện cho bước (7) là O(n³). Vậy thời gian thực hiện toàn bộ giải thuật là ở cấp O(n³).

Giải thuật CYK:

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 V_ij 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ì x₁₁ = x₄₁ = b nên V₁₁ = V₄₁ = {B} vì B là biến duy nhất dẫn xuất ra b, còn x₂₁ = x₃₁ = x₅₁ = a, suy ra V₂₁ = V₃₁ = V₅₁ = {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 V ij

Để tính V_ij 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 V_ik với V_{i+ k, j – k} với k = 1, 2, …, j - 1 để tìm biến D trong V_ik và biến E trong V_{i+ 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 V_ij. 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 V_ij 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 V ij

Chẳng hạn, để tính V₂₄, đầu tiên ta đối chiếu V₂₁ = {A, C} với V₃₃ = {B}. Ta có V₂₁ V₃₃ = {AB, CB}. Vì có các luật sinh S → AB và C → AB nên S và C được đưa vào V₂₄. Tiếp đến ta lại xét V₂₂ V₄₂ = {A}{S, A} = {BS, BA}. Vì có luật sinh A → BA, vậy ta đưa thêm A vào V₂₄. Cuối cùng ta xét V₂₃ V₅₁ = {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 V_24. Vậy V₂₄ = {S, AC}.

Cuối cùng, vì S ∈ V₁₅ , 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.