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

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

1. for Mỗi luật sinh dạng Ak  Aj 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;

1. for Mỗi luật sinh dạng Ak  Ak do

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.