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

Như vậy, *G là bao đóng phản xạ và bắc cầu của G. Nói cách khác,  *G  nếu  được dẫn ra từ  bằng không hoặc nhiều hơn các luật sinh của P. Chú ý rằng  *G  với mọi chuỗi .

Thông thường nếu không có nhầm lẫn ta sẽ dùng các ký hiệu  và * thay cho ký hiệu G và *G. Nếu  dẫn ra  bằng i bước dẫn xuất thì ta ký hiệu  i .

Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh

Cho văn phạm CFG G(V, T, P, S), ta định nghĩa :

L(G) = {ww  T * và S *G w}

Nghĩa là, một chuỗi thuộc L(G) nếu:

1) Chuỗi gồm toàn ký hiệu kết thúc.

2) Chuỗi được dẫn ra từ ký hiệu bắt đầu S.

Ta gọi L là ngôn ngữ phi ngữ cảnh (CFL) nếu nó là L(G) với một CFG G nào đó. Chuỗi  gồm các ký hiệu kết thúc và các biến, được gọi là một dạng câu sinh từ G nếu S *. Hai văn phạm G1, G2 được gọi là tương đương nếu L(G1) = L(G2)

Thí dụ 5.3 : Xét văn phạm G (V, T, P, S), trong đó :

V = {S}, T = {a, b}, P = {S ® aSb, S ® ab}.

Bằng cách áp dụng luật sinh thứ nhất n -1 lần và luật sinh thứ hai 1 lần, ta có:

S Þ aSb Þ aaSbb Þ a3Sb3 Þ ... Þ an-1bn-1 Þ anbn

Vậy, L(G) chứa các chuỗi có dạng anbn, hay L(G) = {anbn  n  1}.

Cây dẫn xuất

Để dễ hình dung sự phát sinh ra các chuỗi trong văn phạm phi ngữ cảnh, ta thường diễn tả một chuỗi dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa như sau:

Định nghĩa : Cho văn phạm G (V, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G được định nghĩa như sau :

i) Mỗi nút (đỉnh) có một nhãn, là một ký hiệu  (V  T  {})

ii) Nút gốc có nhãn là ký hiệu bắt đầu S.

iii) Nếu nút trung gian có nhãn A thì A  V

iv) Nếu nút n có nhãn A và các đỉnh n1, n2, ..., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì A  X1X2 ... Xk là một luật sinh trong tập luật sinh P.

v) Nếu nút n có nhãn là từ rỗng  thì n phải là nút lá và là nút con duy nhất của nút cha của nó.

Thí dụ 5.4 : Xét văn phạm G ({S, A}, {a, b}, P, S), trong đó P gồm:

S ® aAS | a

A ® SbA | SS | ba

Một cây dẫn xuất từ văn phạm có dạng như hình 5.1 sau :

Ta thấy, nút 1 có nhãn S và các con của nó lần lượt là a, A, S (chú ý S  aAS là một luật sinh). Tương tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A  SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S  a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A  ba).

Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi chuỗi này là chuỗi sinh bởi cây dẫn xuất.

Hình 5.1 - Cây dẫn xuất từ văn phạm

Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn được gọi là A-cây con (hoặc A-cây). Cây con cũng giống như cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký hiệu bắt đầu S.

Thí dụ 5.5 :Xét văn phạm và cây dẫn xuất trong Hình 5.1. Đọc các lá theo thứ tự từ trái sang phải ta có chuỗi aabbaa, trong trường hợp này tất cả các lá đều là ký hiệu kết thúc, nhưng nói chung cũng không bắt buộc như thế, lá có thể có nhãn là  hoặc biến. Ta thấy dẫn xuất S * aabbaa bằng chuỗi dẫn xuất :

S Þ aAS Þ aSbAS Þ aabAS Þ aabbaS Þ aabbaa