Chuẩn hóa văn phạm phi ngữ cảnh

Dạng chuẩn Chomsky - CNF (Chomsky Normal Form)

ĐỊ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 G₁(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 → X₁X₂ ... X_m (m >1). Nếu X_i là ký hiệu kết thúc a thì ta đưa thêm một biến mới C_a và luật sinh mới C_a → a. Thay thế X_i bởi C_a, 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 G₂ (V’, T, P’, S). Nếu α ⇒_G1 β thì α ⇒*_G2 β. Vậy L(G₁) ⊆ L(G₂). 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 → B 1 B 2 ... B m (m > 1). Ta có thể viết w = w 1 w 2 ...w m trong đó B i ⇒ * G2 w i , 1 ≤ i ≤ m. Nếu B i là ký hiệu kết thúc a i nào đó thì w i là a i . Theo cách xây dựng P’ ta có luật sinh A → X 1 X 2 ... X m của P trong đó X i = B i nếu B i ∈ V và X i = a i nếu B i ∈ V’- V. Với B i ∈ V, ta đã biết rằng có dẫn xuất B i ⇒ * G1 w i bằng ít hơn k bước, do vậy theo giả thiết quy nạp X i ⇒ * G1 w i . 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 → B 1 B 2 ... B m (m ≥ 2) với A, B 1 , ... ,B m là các biến và a là ký hiệu kết thúc. Ta sửa G 2 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 → B₁B₂ ... B_m (m > 2) . Ta thay bằng tập hợp các luật sinh : A → B₁D₁

D₁ ® B₂D₂

...

D_{m - 3} ® B_{m - 2}D_{m - 2}

D_{m - 2} ® B_{m - 1}B_m

Đặ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 G₃ (V’’, T, P’’, S). Ta có G₃ 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(G₂) ⊆ L(G₃). Ngược lại cũng đúng tức là, L(G₃) ⊆ L(G₂). Chúng ta cũng đã có L(G₂) ⊆ L(G₁) và L(G₁) ⊆ L(G₂). Vậy G₃ 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 C_a, C_b và 2 luật sinh mới C_a ® a và C_b ® b.

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

S ® C_aA | a | C_bB | b | ABA

A ® C_aA | a | C_bB | b

B ® C_bB | b

C_a ® a

C_b ® 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 ® C_aA | a | C_bB| b | AD1

A ® C_aA | a | C_bB| b

B ® C_bB| b

C_a ® a

Cb ® b

D 1 ® 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.

Dạng chuẩn Greibach GNF (Greibach Normal Form)

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 ® α₁Bα₂ là luật sinh trong P và B ® β₁ | β₂ | ... | β_r là các B - luật sinh; văn phạm G₁ (V, T, P₁, S) thu được từ G bằng cách loại bỏ luật sinh A ® α₁Bα₂ và thêm vào luật sinh A ® α₁β₁α₂ | α₁β₂α₂ | ... | α₁β_rα₂ thì L(G) = L(G₁)

Chứng minh

. Hiển nhiên L(G₁) ⊆ L(G) vì nếu A ® α₁β_iα₂ được dùng trong dẫn xuất của G₁ thì ta dùng A ⇒_G α₁Bα₂⇒_G α₁β_iα₂

. Để chỉ ra L(G) ⊆ L(G₁) ta cần chú ý rằng A ® α₁Bα₂ là luật sinh trong P - P₁ (có trong G và không có trong G₁). Bất cứ khi nào luật sinh A ® α₁Bα₂ đượ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 ® α₁Bα₂ ⇔ A ⇒_G1 α₁β_iα₂

B ® β_i

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

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α₁ | Aα₂ | ... | 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 ® β₁ | β₂ | ... | β_s là các A - luật sinh còn lại; G₁ (V  {B}, T, P₁, 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(G₁).

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 G₁ 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(G₁).

ĐỊ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 A₁, A₂, ..., A_m (m ≥ 1) với A₁ là ký hiệu bắt đầu. Đặt V = {A₁, A₂, ..., A_m}.

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

Bắt đầu từ A₁ và tiến tới A_m, ta thay thế các A_k - luật sinh :

Nếu A_k → A_jγ size 12{γ} {}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ế A_j bên vế phải của mỗi A_j - 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 A_k → A_lγ size 12{γ} {} 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 B_k.

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

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) A_i → A_jγ size 12{γ} {} với j > i

2) A_i → a γ size 12{γ} {} với a Î T

3) B_k ® γ size 12{γ} {}γ size 12{γ} {} Î (V È {B₁, B₂ , ..., B_{i - 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 A_m phải là một ký hiệu kết thúc, vì A_m 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 A_m-1- luật sinh bất kỳ phải là A_m hoặc một ký hiệu kết thúc. Nếu là A_m, ta tạo ra tập luật sinh mới bằng cách thay thế A_m bởi chuỗi vế phải của các A_m-luật sinh theo bổ đề 3. Tiếp tục quá trình này cho các luật sinh từ A_m-2, ..., A₂, A₁ cho tới khi vế phải của tất cả các A_i - 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 B₁, B₂, ..., B_m.

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 A_i -luật sinh, với 1 ≤ i ≤ n, bắt đầu bằng ký hiệu kết thúc hoặc A_jA_k 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 B_j khác, hay tất cả B_i - luật sinh đều có vế phải bắt đầu bằng ký hiệu kết thúc hoặc A_i. Một lần nữa, lại áp dụng bổ đề 3 cho mỗi B_i - 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 :

A₁ ® A₂A₁ | A₂A₃

A₂ ® A₃A₁ | a

A₃ ® A₂A₂ | 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 = {A₁, A₂, ..., A₃}

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

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

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 :

A₁ ® A₂A₁ | A₂A₃

A₂ ® A₃A₁ | a

A₃ ® aA₂ | b | aA₂B| bB

B ® A₁A₂ | A₁A₂ B

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

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

A₁ ® aA₂A₁A₁ | bA₁A₁ | aA₂BA₁A₁ | bBA₁A₁ | aA₁|

aA₂A₁A₃ | bA₁A₃ | aA₂BA₁A₃ | bBA₁A₃ | aA₃

A₂ ® aA₂A₁ | bA₁ | aA₂BA₁| bBA₁| a

A₃ ® aA₂ | b | aA₂B| bB

B ® A₁A₂ | A₁A₂ B

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

B ® aA₂A₁A₁A₂ | bA₁A₁A₂ | aA₂BA₁A₁A₂ | bBA₁A₁A₂ | aA₁A₂

| aA₂A₁A₃A₂ | bA₁A₃A₂ | aA₂BA₁A₃A₂ | bBA₁A₃A₂ | aA₃A₂

|aA₂A₁A₁A₂B | bA₁A₁A₂B | aA₂BA₁A₁A₂B | bBA₁A₁A₂B | aA₁A₂ B

| aA₂A₁A₃A₂B | bA₁A₃A₂B | aA₂BA₁A₃A₂B | bBA₁A₃A₂B | aA₃A₂B

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