Ngôn ngữ hình thức - 16

Nếu G = (N, T, P, S) là CFG thì ta có thể tìm được CFG G‟ = (N‟, T‟, P‟, S) tương đương sao cho mỗi X  N‟  T‟ tồn tại α, β  (N‟  T‟)* để S * αXβ.

Chứng minh:

Tập N‟  T‟ gồm các ký tự xuất hiện trong dạng câu của G được xây dựng bởi giải thuật lặp như sau:

Bước1: Đặt N‟ = {S}; T‟ = ∅;

Bước2: Với mỗi A  N‟ thực hiện

- Tìm tất cả các luật sinh A → α | α | ... | α là các luật sinh trong P

1 2 n

- Nếu có thì thêm tất cả các biến của α , α , ... , α vào N‟ và các ký tự

1 2 n

kết thúc của α , α ,..., α vào T‟.

1 2 n

Bước3: Lặp lại bước 2 cho đến khi không còn biến hoặc ký tự kết thúc nào được thêm vào nữa.

Dễ thấy, X  N‟  T‟ thì tồn tại α, β  (N‟  T‟)* để S * αXβ, trong đó P‟ là tập hợp tất cả các luật sinh của P chỉ chứa các ký tự thuộc (N‟  T‟).

Ta dễ dàng chứng minh L(G‟) = L(G) .

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

5) Giải thuật loại bỏ ký hiệu không được dẫn xuất ra từ ký hiệu bắt đầu

Input G = (N, T, P, S) - CFG

Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi ký hiệu của nó đều được dẫn xuất ra từ ký hiệu bắt đầu và L(G‟) = L(G)

Process

Bước1: Khởi tạo

S‟ = S; N‟ = {S}; T‟ = ∅

Bước2: Xác định N‟, T‟

+ Với mỗi A  N‟ thực hiện

- Tìm tất cả các luật sinh A → α1| α2 | ... | αn là các luật sinh trong P

- Nếu có thì thêm tất cả các biến của α1, α2, ... , αn vào N‟ và các ký tự kết thúc của α1, α2 ,..., αn vào T‟ ;

Bước3: Quay lại bước 2 cho đến khi gặp một lượt không còn biến hoặc ký tự kết thúc nào được thêm vào N‟ và T‟ nữa.

Bước 4: xác định p’

P‟ ={ A → X X ... X  P  AN‟ và X (N‟ T‟)* i}

1 2 n i

Ví dụ 1: Loại bỏ ký tự không được dẫn xuất ra từ ký hiệu bắt đầu trong văn phạm sau: G = (N, T, P, S):

N = S, A, B, C, D

T = a, b, c, d S = S;

P: có các luật sinh sau:

S → AB | a;

A → a;

C → b;

D → bA.

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

S‟ = S;

2. N‟, T‟:

Bước

N‟	T‟	Giải thích
KT	{S}		
1	{S, A, B}	{a}	S → AB a
2	{S, A, B}	{a}	A → a

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

• Ngôn ngữ hình thức - 13
• 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
• Dạng Chuẩn Chomsky - Cnf (Chomsky Normal Form)
• 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

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

3. P‟= {S → AB a; A → a}.

Ví dụ2: Loại bỏ các ký thừa trong văn phạm trên

- Theo ví dụ trên loại bỏ ký tự không được sinh ra từ ký hiệu bắt đầu ta có văn phạm với tập luật sinh: S → AB  a; A → a.

- Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc, ta thu được văn phạm với tập luật sinh: S → a

Như vậy, để loại bỏ các ký thừa trong văn phạm phi ngữ cảnh, ta chỉ việc thực hiện hai công việc: Loại bỏ các biến không sinh ra ký tự kết thúc và các ký tự không được dẫn xuất ra từ ký hiệu bắt đầu. Từ đó ta có định lý.

6) Định lý

Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng được sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký tự thừa.

Chứng minh:

Đặt L = L(G) là CFL không rỗng.

Đặt G là kết quả của việc áp dụng bổ đề 1 vào G và G là kết quả của việc áp

1 2

dụng bổ đề 2 vào G .

1

Giả sử G

2

có ký tự thừa là X. Theo bổ đề 2 ta có S *

G2

αXβ. Vì tất cả các ký tự

trong G

2

đều có trong G

1

nên theo bổ đề 1: S *

αXβ *

G1

w với w là xâu ký tự kết

G1

thúc. Vì vậy không có ký tự nào trong dẫn xuất αXβ *G1 w bị loại bỏ bởi bổ đề 2, vậy X dẫn ra ký tự kết thúc trong G2 . Suy ra X là ký tự không thừa (mâu thuẫn).

Vậy văn phạm G2 không có ký tự thừa nào.

Ví dụ: Cho văn phạm G = (N, T, P, S):

N = S, , , C, D T = a, b, c

S = S;

P: S a;  a;

S b;  b;

D  c; A  BC;

Hãy loại bỏ các ký tự thừa trong văn phạm trên.

- Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc: 1. G‟= (N‟, T‟, P‟, S‟):

T‟ = a, b, c S‟ = S; 2. N‟:

Bước

N‟	Giải thích
KT	{A, B, D}	B → a; A → b; D → c
1	{S, B, D, A}	S a; S b; B → a; A → b; D → c
2	{S, A, B, D}	S a; S b; B → a; A → b; D → c

3. P‟= {S →Aa; S → Bb; B → a; A → b; D → c }.

- Áp dụng giải thuật loại bỏ các ký tự không được dẫn xuất ra từ ký hiệu bắt đầu: 1. G” = (N”, T”, P”, S”):

S” = S;

2. N” và T”:

Bước

N”	T”	Giải thích
KT	{S}	
1	{S , A, B}	{a, b}	S a; S b
2	{S, A, B}	{a, b}	S a; S b; A → b;  a

3. P” = {S → Aa; S → Bb; A → b; B → a}.

Khi đó L(G) = L(G”) và G” không chứa ký hiệu thừa.

3.2.2. Luật sinh ε (ε quy tắc)

1) Định nghĩa

- Một luật sinh có dạng A → ε được gọi là luật sinh ε (ε quy tắc).

- Một biến A được gọi là biến rỗng (nullable) nếu A + ε

Ta xét đến việc loại bỏ các luật sinh ε. Nếu ε  L(G) thì không thể loại được tất cả các luật sinh ε, nhưng nếu ε ∉ L(G) thì có thể. Phương pháp loại bỏ dựa trên việc xác định liệu một biến A có là biến rỗng hay không ?. Ta có thể thay thế mỗi luật sinh B → X1X2 ... Xn bằng tất cả các luật sinh được định dạng bởi việc xóa bỏ tập hợp con các biến Xi rỗng, nhưng không bao gồm luật sinh B → ε, ngay cả khi tất cả các Xi đều là biến rỗng.

2) Bổ đề 3 (Dùng để loại bỏ luật sinh ε)

Cho CFG G = (N, T, P, S) với ε L(G), có một CFG G‟= (N‟, T, P‟, S)

tương đương sao cho G‟ không chứa luật sinh ε.

Chứng minh:

Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp như sau:

- Bắt đầu, nếu A → ε là một luật sinh thì A là biến rỗng.

- Kế tiếp, nếu B → α, trong đó α gồm toàn các ký tự là các biến rỗng đã được tìm thấy trước đó thì B cũng là biến rỗng.

- Lặp lại cho đến khi không còn biến rỗng nào được tìm thấy nữa.

Tập luật sinh P‟ được xây dựng như sau: Nếu A → X X ... X là một luật sinh trong

1 2 n

P thì ta thêm tất cả các luật sinh A → α α ... α vào P‟ với điều kiện:

1 2 n

1. Nếu X không là biến rỗng thì α = X ;

i i i

2. Nếu X là biến rỗng thì α là X hoặc ε;

i i i

3. Không phải tất cả α đều bằng ε.

i

‟

Đặt G‟ = (N, T, P‟, S). Ta sẽ chứng minh rằng với mọi A  N và w T*; A * w nếu và chỉ nếu w ≠ ε và A * w.

G G

- Thuận:

i

‟‟

Đặt A  w và w ≠ ε, ta chứng minh quy nạp rằng A * w.

G G

Nếu i = 1 ta có A → w là một luật sinh trong P, và vì w ≠ ε nên luật sinh này cũng thuộc P‟.

Giả sử kết quả đúng tới i - 1 (i >1)

Xét A 

X X ...X

i -1



w. Ta viết w = w w

...w

sao cho với j, X * w .

G 1 2 n G 1 2 n j j

‟‟

Nếu w ≠ ε và X là biến thì theo giả thiết quy nạp, ta có X * w (vì dẫn

j j j G j

xuất X * w có ít hơn i bước). Nếu w = ε thì X là biến rỗng, vậy A → β β ...β là

j j j j 1 2 n

một luật sinh trong P‟, trong đó β = X nếu w ≠ ε và β = ε nếu w = ε.

j j j j j

Vì w ≠ ε nên không phải tất cả β là ε. Vậy, ta có dẫn xuất:

j

A  β β ...β

* w β ...β

* w w β ...β

* ... * w w ...w

= w trong G‟‟.

1 2 n

- Đảo:

1 2 n

1 2 3 n

1 2 n

Giả sử A iG‟ w. Chắc chắn rằng w ≠ ε vì G‟ không có luật sinh ε. Ta quy nạp theo i rằng A *G w.

Nếu i = 1: Ta thấy A → w là một luật sinh trong P‟, do đó cũng phải có luật

sinh A → w trong P sao cho bằng việc loại bỏ các ký tự rỗng trong α, ta có w. Vậy,

có tồn tại dẫn xuất A  α * w, trong đó α * w liên quan đến các dẫn xuất ε từ

G G

các biến rỗng của α mà chúng ta đã loại bỏ khỏi w.

Giả sử kết quả đúng tới i - 1 (i >1)

i - 1

‟

Xét A  X X

G 1 2

... X

n

G‟ w. Phải có luật sinh A → β trong P sao cho

X1X2 ... Xn tìm được khi loại bỏ các biến rỗng của β. Vậy A *G X1X2 ...Xn (chứng minh tương tự như ở trên). Ta viết w = w1w2 ...wn sao cho với j ta có Xj *G‟ wj (bằng ít hơn i bước). Theo giả thiết quy nạp Xj *G‟ wj nếu Xj là biến. Nếu Xj là ký tự kết thúc thì wj = Xj và Xj *G wj là hiển nhiên. Vậy A *G w.

Hơn nữa S *G‟ w nếu và chỉ nếu S *G w. Vậy L(G‟) = L(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 

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‟ = ;

R = {AN‟  A →  P}

Bước2: Tìm Tập các biến rỗng R

Với mỗi luật sinh A → X1X2 ... Xn P kiểm tra Nếu Xi R i thì R = R{A};

Bước3: Quay lại bước 2 cho đến khi không còn biến rỗng nào được thêm vào

R nữa.

Bước4: Xác định P‟

Với mỗi luật sinh A → X1X2 ... Xn P không là luật sinh ε thực hiện Thêm tất cả các luật sinh A → α1α2 ... αn vào P‟ với điều kiện:

1. Nếu Xi không là biến rỗng thì αi = Xi;

2. Nếu Xi là biến rỗng thì αi là Xi hoặc ε;

3. Không phải tất cả α đều bằng ε.

i

Chú ý: Trong trường hợp L(G), muốn có một văn phạm thực sự tương đương với văn phạm G thì sau khi loại bỏ các luật sinh , ta phải bổ sung thêm luật sinh S → ε vào tập luật sinh của G‟.

Ví dụ: Loại bỏ luật sinh ε trong văn phạm sau:

S → AB;

A → aA | ε; B → bB | ε.

- Áp dụng giải thuật trên, ta có tập các biến rỗng:

Bước

R-Nullable	Giải thích
KT	{A, B}	A → ε; B → ε
1	{A, B, S}	S → AB
2	{A, B, S}	S → AB

 Tập biến rỗng Nullable = {A, B, S}

- Tập luật sinh P‟:

S → AB | A | B; A → aA | a;

B → bB | b.

Vì L(G) nên phải bổ sung thêm luật sinh S → ε vào P‟.

4) Định lý

Nếu L = L(G) với CFG G = (N, T, P, S) thì L - {ε} là L(G‟) với CFG G‟

không có ký tự thừa và không có luật sinh ε.

Chứng minh:

- Trước hết, thực hiện loại bỏ luật sinh ε trong G để thu được G”.

- Tiếp theo, thực hiện loại bỏ các ký hiệu thừa trong G” để thu được G‟.

Vì thực hiện loại bỏ các ký hiệu thừa trong G” không đưa ra thêm luật sinh mới nào nên G‟ không có chứa ký tự là biến rỗng hay ký tự thừa.

3.2.3. Luật sinh đơn vị

1) Định nghĩa

Một luật sinh có dạng A → B với A, B đều là biến (ký tự không kết thúc) gọi là luật sinh đơn vị.

2) Bổ đề 4 (Dùng để loại bỏ luật sinh đơn vị)

Cho CFG G = (N, T, P, S) với ε  L(G), có một CFG G‟= (N, T, P‟, S)

tương đương sao cho G‟ không chứa luật sinh đơn vị.

Chứng minh:

Đặt L là CFL không chứa ε và L = L(G) với G = (N, T, P, S) là một CFG nào đó. Theo định lý trên, xây dựng tập hợp mới P‟ gồm các luật sinh từ P như sau:

- Đầu tiên đưa các luật sinh không là luật sinh đơn vị vào P‟.

- Sau đó, nếu có suy dẫn dạng A + B với A, B  N thì thêm vào P‟ tất cả các luật sinh dạng A → α, với B→ α không phải là luật sinh đơn vị của P.

Chú ý rằng ta có thể dễ dàng kiểm tra có hay không A +G B vì G không có luật sinh ε và nếu A G B1 G B2 G ... G B (trong đó một vài biến nào đó có thể xuất hiện 2 lần) thì ta có thể tìm một chuỗi rút ngắn hơn A +GB. Vì vậy, ta chỉ xét các luật sinh đơn vị không có biến lặp lại.

Bây giờ ta sửa lại văn phạm G‟= (N, T, P‟, S). Chắc chắn rằng nếu A → α là một luật sinh trong P‟ thì A +G α. Vậy nếu có dẫn xuất trong G‟ thì có dẫn xuất trong G. Giả sử rằng w  L(G). Xét dẫn xuất trái của w trong G:

S G α0 G α1 G ... G αn = w.

Nếu 0 ≤ i < n thì nếu trong G có αi G αi+1 bằng luật sinh không là luật sinh đơn vị thì trong G‟ cũng có αi G‟ αi+1 không là luật sinh đơn vị. Giả sử αi G αi+1 bằng luật sinh đơn vị, nhưng bước dẫn xuất trước đó αi - 1  αi không phải bằng luật sinh đơn vị hoặc i = 0. Và chuỗi dẫn xuất trong G từ αi + 1 G αi + 2 G ... G αj tất cả đều bằng luật sinh đơn vị, còn từ αj G αj+1 không là luật sinh đơn vị thì ta thấy tất cả các αi, αi+1, …, αj sẽ có cùng độ dài và vì chuỗi dẫn xuất là dẫn xuất trái nên