Dạng Chuẩn Chomsky - Cnf (Chomsky Normal Form)

các ký tự 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‟).

Từ việc chứng minh bổ đề trên, ta có giải thuật sau.

3) Giải thuật loại bỏ luật sinh đơn vị

Input G = (N, T, P, S) – CFG, L(G)

Output G‟= (N‟, T‟, P‟, S‟) – CFG, G‟ không chứa luật sinh  và L(G‟) = L(G) Process

Bước1: Khởi tạo

N‟ = N; T‟ = T; S‟ = S; P‟ = {AP A không là lật sinh đơn vị }

Có thể bạn quan tâm!

• Văn Phạm Phi Ngữ Cảnh Và Automat Đẩy Xuống
• Quan Hệ Giữa Dẫn Xuất Và Cây Dẫn Xuất
• Ngôn ngữ hình thức - 16
• 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)
• Ngôn ngữ hình thức - 19
• Ngôn ngữ hình thức - 20

Xem toàn bộ 254 trang tài liệu này.

Bước2: Xây dựng P‟

- Với mỗi biến AN‟ thực hiện: tìm ΔA = {B N‟ | A + B}

- Với mỗi biến AN‟ và ΔA thực hiện: Với mỗi B ΔA thực hiện:

+ Tìm các luật sinh B → α  P‟;

+ Thêm vào P‟ tất cả các luật sinh dạng A → α.

Ví dụ: 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.

Áp dụng giải thuật trên, ta có G‟= (N‟, T‟, P‟, S‟):

- N‟ = {E, T, F}; T‟ = {+, *, (, ), a} ; S‟ = E ;

P‟ = {E → E + T ; T → T * F; F → (E) | a}

- Δ E = {T, F}; Δ T = {F}; Δ F = 

- Với biến E, phải thêm vào P‟ các luật sinh E → T * F | (E) | a;

- Với biến T, phải thêm vào P‟ các luật sinh T → (E) | a;

Vậy tập luật sinh P‟, theo giải thuật 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.

4) Định lý

Mỗi CFL không chứa ε được sinh ra bởi CFG không có ký tự thừa, luật sinh ε hoặc luật sinh đơn vị .

Chứng minh:

Chỉ việc áp dụng các giải thuật trên để loại bỏ: các luật sinh đơn vị, luật sinh

, các ký tự thừa sẽ thu được một văn phạm thỏa mãn điều kiện của định lý.

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

Phần trên ta đã xem xét vấn đề rút gọn văn phạm phi ngữ cảnh để nhận được văn phạm tối giản. Tuy nhiên chỉ như vậy thôi chưa đủ. Khi viết các chương trình dịch, chương trình sẽ phức tạp lên rất nhiều nếu mỗi quy tắc sinh có nhiều dạng khác nhau. Vấn đề đặt ra là liệu có thể đưa ra các quy tắc sinh của P về cùng một dạng nào đó được không. Việc đưa các quy tắc sinh của văn phạm phi ngữ cảnh về các dạng chung được gọi là chuẩn hoá văn phạm phi ngữ cảnh.

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

1) Định nghĩa

Văn phạm phi ngữ cảnh G = (N, T, P, S) có L(G) được gọi là ở dạng chuẩn Chomsky (CNF) nếu các luật sinh của nó chỉ có một trong hai dạng A → BC hoặc A → a, với A, B, C  N và a T.

2) Định lý

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 ở dạng chuẩn Chomsky nào đó.

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: Khử luật sinh đơn vị dạng A → B, với A, B là biến (ký tự không kết

thúc).

Theo định lý ở phần trước, ta có thể tìm được CFG tương đương G = (N, T, P1, S)

1

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ý tự thì đó phải là ký tự 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ý tự kết thúc.

Xét luật sinh trong P có dạng A → X X ... X (m >1). Nếu X là ký tự kết

1 2 m i

thúc a thì ta đưa thêm một biến (ký tự không kết thúc) mới C và luật sinh mới C →

a a

a. Thay thế X bởi C , gọi tập các biến (ký tự không kết thúc) mới là N‟ và tập luật

i a

sinh mới là P‟.

Xét CFG G = (N‟, T, P‟, S). Nếu α  β thì α * β. Vậy L(G )  L(G ).

2 G1 G2 1 2

Ta chứng minh quy nạp theo số bước dẫn xuất rằng nếu A * w, với A N và w

G2

*

T thì A

* w.

G1

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ý tự 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

N và Xi = ai nếu Bi N‟- N. Với Bi  N, 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 với m  2 và A, B1, B2, …, Bm là các biến (ký tự không kết thúc); a là ký tự 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ý tự chưa kết thúc.

Xét luật sinh trong P‟có dạng A → B1B2…Bm (m  2). Ta bổ sung thêm m- 2 biến mới D1, D2,… , Dm - 2 và thay nó bằng tập các luật sinh:

A → B1D1 ;

D1 → B2D2 ;

...

Dm - 3 → Bm - 2Dm - 2;

Dm - 2 → Bm - 1Bm .

Đặt N” là tập các biến (ký tự không kết thúc) mới, P” là tập các luật sinh mới và văn phạm mới G3 = (N”, 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.

Từ việc chứng minh định lý, có thể rút ra giải thuật sau.

3) Giải thuật biến đổi văn phạm phi ngữ cảnh về dạng chuẩn Chomsky

Input G = (N, T, P, S) – CFG, L(G)

Output G‟= (N‟, T‟, P‟, S) – ở dạng chuẩn Chomsky và L(G‟) = L(G) Process

Bước1: Khử luật sinh đơn vị

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

Với mỗi luật sinh trong P có dạng A → X1X2 ... Xm (m >1) thực hiện Nếu Xi là ký tự kết thúc a thì

- Thêm vào một biến mới Ca

- Thêm vào một luật sinh mới Ca → a.

- Thay thế Xi bởi Ca

(tập các biến mới là N‟ và tập luật sinh mới là P‟)

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

Ví dụ:

Với mỗi luật sinh trong P‟có dạng A → B B2…Bm (m  2) thực hiện

1

- Thêm vào N‟ m-2 biến mới D , D ,… , D

1 2 m - 2

- Thay nó bằng tập các luật sinh: A → B D ;

1 1

D → B D ;

1 2 2

...

D → B D ;

m - 3 m - 2 m - 2

D → B B .

m - 2 m - 1 m

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: Khử các luật sinh đơn vị

Gọi tập Δ

A

= {B | A * B }, xét các biến (ký tự không kết thúc) trong văn phạm, ta có:

Δ = {A, B };

S

Δ = {B};

A

Δ = {}.

B

Sau khi bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị ta có:

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ý tự 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 (ký tự không kết thúc) 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.

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

1) Các định nghĩa

- Văn phạm phi ngữ cảnh G = (N, T, P, S) có  L(G) được gọi là ở dạng chuẩn Greibach (GNF) nếu các luật sinh của nó chỉ có một dạng A → aα với A N; a  T và α  (N T)*.

- Một luật sinh có dạng A → α (biến A ở bên trái) với A N, α  (NT)*

được gọi là A – luật sinh.

- Một văn phạm phi ngữ cảnh được gọi là đệ quy trái trực tiếp nếu tồn tại một luật sinh có dạng A → Aα với A N, α  (NT)*.

2) Bổ đề 1 (Dùng thay thế các luật sinh trực tiếp)

Cho G = (N, T, P, S) là một CFG, A → α1Bα2 và các B - luật sinh B → β1 | β2

| ... | βr là các luật sinh trong P; văn phạm G1= (N, 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 các 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 và B → βi  A G1 α1βiα2 Vậy L(G) = L(G1)

3) Bổ đề 2 (Dùng loại bỏ luật sinh dạng đệ quy trái trực tiếp trong văn phạm)

G = (N, T, P, S) là một CFG; A → Aα1 | Aα2 | ... | Aαr | β1 | β2 | ... | βs là tập các A - luật sinh; G1= (N  {B}, T, P1, S) là CFG được tạo ra từ G bằng cách thêm vào N biến mới B và thay các A - luật sinh bằng tập các luật sinh dạng:

1. A → βi B | β1 | β2 | ... | βs với 1 ≤ i ≤ s

2. B → αi B | αi với 1 ≤ i ≤ r thì L(G) = L(G1).

Chứng minh:

Trong một dãy 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

Dãy dẫn xuất trong G có thể thay bằng dãy 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).

4) Định lý (Dạng chuẩn Greibach - GNF)

Mỗi CFL bất kỳ không chứa ε được sinh ra bởi một CFG ở dạng chuẩn Greibach – GNF.

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 (ký tự không kết thúc) trong tập của G‟ thành A1, A2, ..., Am (m ≥ 1) với A1 là ký tự bắt đầu. Đặt N = {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ằng cách:

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

Nếu Ak → Ajγ là luật sinh với j < k thì sinh ra một tập luật sinh mới bằng cách thay thế Aj bên vế phải bằng vế phải của mỗi Aj - luật sinh theo bổ đề 1. 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ổ đề 2 bằng cách đưa vào

các biến (ký tự không kết thúc) mới Bk.

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

For k:= 1 to m do begin

for j:= 1 to k-1 do

for Mỗi luật sinh dạng Ak → Ajα do begin

for Tất cả luật sinh Aj → β do Thêm luật sinh Ak → βα;

Loại bỏ luật sinh Ak → Ajα end;