Các ký hiệu vô ích

Một ký hiệu X gọi là có ích nếu có một dẫn xuất S ⇒* αXβ ⇒* w với các chuỗi α, β bất kỳ và w ∈ T ^*. Ngược lại X gọi là vô ích.

Vậy, có 2 đặc điểm cho ký hiệu có ích:

- X phải dẫn ra một chuỗi ký hiệu kết thúc.

- X phải nằm trong dẫn xuất từ S.

Tuy nhiên 2 dấu hiệu trên không đủ để đảm bảo X có ích vì X có thể nằm trong dạng câu chứa một biến nhưng từ đó không có ký hiệu kết thúc được sinh ra.

BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)

Cho CFG G (V, T, P, S) với L(G) ≠ ∅, có một CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi A ∈ V’ tồn tại w ∈ T* để A ⇒* w.

Chứng minh

Mỗi biến A với luật sinh A → w trong P thì rõ ràng A ∈ V’. Nếu A → X₁X₂ ... X_n là một luật sinh, trong đó mỗi X_i hoặc là ký hiệu kết thúc hoặc là một biến đã có sẵn trong V’ thì một chuỗi các ký hiệu kết thúc có thể được dẫn ra từ A bằng dẫn xuất bắt đầu A ⇒ X₁X₂ ... X_n, vì vậy A ∈ V’. Tập V’ có thể tính được bằng cách lặp lại giải thuật trên. P’ là tập tất cả các luật sinh mà các ký hiệu của nó thuộc V’  T.

Giải thuật tìm V' như sau:

Rõ ràng rằng nếu biến A được thêm vào V’ tại bước (2) hoặc (5) thì A sẽ dẫn ra được chuỗi ký hiệu kết thúc. Ta chứng minh rằng nếu A dẫn ra được một chuỗi ký hiệu kết thúc thì A được thêm vào tập NEWV.

Dùng chứng minh quy nạp theo độ dài của dẫn xuất A ⇒ * w.

Nếu độ dài bằng 1 thì A → α là một luật sinh trong P. Vậy A được đưa vào V’ tại bước (2).

Giả sử kết quả đúng tới k -1 bước dẫn xuất ( k >1)

Nếu A ⇒ X 1 X 2 ... X n ⇒ * w bằng k bước thì ta có thể viết w = w 1 w 2 ... w n , trong đó X i ⇒ * w i , với 1 ≤ i ≤ n bằng ít hơn k bước dẫn xuất. Theo giả thiết quy nạp thì các biến X i này được thêm vào V’. Khi X i cuối cùng được thêm vào V’ thì vòng lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ được thêm vào V’ tại (5).

Ta chứng minh L(G’) = L(G) :

Chọn V’ là tập hợp tại (6) và P' là tập tất cả các luật sinh mà các ký hiệu của nó thuộc (V’  T) thì chắc chắn rằng có tồn tại văn phạm G’ (V’, T, P’, S) thoả mãn tính chất: nếu A ∈ V’ thì A ⇒ * w với w nào đó thuộc T * . Hơn nữa, mỗi luật sinh của P’ đều là luật sinh của P nên ta có L(G’) ⊆ L(G).

Ngược lại giả sử một từ w ∈ L(G) - L(G’) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc V – V’ hoặc luật sinh thuộc P – P’ (các dẫn xuất này đưa ra các biến thuộc V – V’), nhưng do không có biến nào trong V – V’ dẫn đến chuỗi kết thúc, điều này dẫn đến mâu thuẫn.

Vậy L(G’) = L(G).

Hay có thể nói 2 ngôn ngữ được cho từ 2 văn phạm G và G’ là tương đương nhau, hay nói cách khác: nếu có một văn phạm G thì luôn luôn có một văn phạm G’ tương ứng mà trong đó mỗi biến của G’ đều cho ra ký hiệu kết thúc.

BỔ ĐỀ 2: (Dùng loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu văn phạm)

Nếu G (V, T, P, S) là CFG thì ta có thể tìm được CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi X ∈ V’ $$T’ tồn tại α, β ∈ (V’ $$ T’)* để S ⇒^* αXβ.

Chứng minh

Tập V’  T’ gồm các ký hiệu 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 :

. Đặt V’ = {S}; T’ = ∅;

. Nếu A ∈ V’ và A → α₁| α₂ | ... | α_n là các luật sinh trong P thì thêm tất cả các biến của α₁, α₂, ... , α_n vào V’ và các ký hiệu kết thúc của α₁, α₂ ,..., α_n vào T’.

. Lặp lại giải thuật cho đến khi không còn biến hoặc ký hiệu kết thúc nào được thêm vào nữa.

Dễ thấy, X ∈ V’ $$ T’ thì tồn tại α, β ∈ (V’ $$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ý hiệu thuộc (V’ $$ T’).

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

ĐỊNH LÝ 5.2: 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ý hiệu vô ích.

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 dụng bổ đề 2 vào G₁.

Giả sử G₂ có ký hiệu vô ích là X. Theo bổ đề 2 ta có S ⇒*_G2 αXβ. Vì tất cả các ký hiệu trong G₂ đều có trong G₁ nên theo bổ đề 1: S ⇒*_G1 αXβ ⇒*_G1 w với w là chuỗi ký hiệu kết thúc. Vì vậy không có ký hiệu 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ý hiệu kết thúc trong G₂ . Suy ra X là ký hiệu có ích (mâu thuẫn).

Vậy văn phạm G₂ không có ký hiệu vô ích nào.

Thí dụ 5.9 : Xét văn phạm có các luật sinh sau :

S ® AB | a

A ® a

Áp dụng bổ đề 1, ta thấy không có ký hiệu kết thúc được nào dẫn ra từ B nên ta loại bỏ B và luật sinh S → AB. Tiếp tục, áp dụng bổ đề 2 cho văn phạm :

S ® a

A ® a

Ta thấy chỉ có S xuất hiện trong dạng câu. Vậy ({S}, {a}, {S ® a}, S) là văn phạm tương đương với văn phạm đã cho và không có ký hiệu vô ích.

Luật sinh ε

Một luật sinh có dạng A → ε gọi là luật sinh ε.

Ta xét đến việc loại bỏ các luật sinh này. 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ó dẫn xuất A ⇒* ε hay không ? Nếu có, ta gọi A là biến rỗng (nullable). Ta có thể thay thế mỗi luật sinh B → X₁X₂ ... X_n 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 X_i rỗng, nhưng không bao gồm luật sinh B → ε, ngay cả khi tất cả các X_i đều là biến rỗng.

ĐỊNH LÝ 5.3 : Nếu L = L(G) với CFG G (V, T, P, S) thì L - { ε } là L(G’) với CFG G’ không có ký hiệu vô ích và không có 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ý hiệu 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_n là một luật sinh trong P thì ta thêm tất cả các luật sinh A → α₁α₂ ... α_n vào P’ với điều kiện :

1) Nếu X_i không là biến rỗng thì α_i = X_i;

2) Nếu X_i là biến rỗng thì α_i là X_i hoặc ε;

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

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

Nếu: Đặt A ⇒ i G w và w ≠ ε , ta chứng minh quy nạp rằng A ⇒ * G’’ w.

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 ⇒ G X 1 X 2 ...X n ⇒ i -1 G w. Ta viết w = w 1 w 2 ...w n sao cho ∀ j, X j ⇒ * w j .

Nếu w j ≠ ε và X j là biến thì theo giả thiết quy nạp, ta có X j ⇒ * G’’ w j (vì dẫn xuất X j ⇒ * w j có ít hơn i bước). Nếu w j = ε thì X j là biến rỗng, vậy A → β 1 β 2 ... β n là một luật sinh trong P', trong đó β j = X j nếu w j ≠ ε và β j = ε nếu w j = ε .

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

A Þ β 1 β 2 ... β n Þ * w 1 β 2 ... β n Þ * w 1 w 2 β 3 ... β n Þ * ... Þ * w 1 w 2 ...w n = w trong G’’.

Chỉ nếu : 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ý hiệu rỗng trong α , ta có w. Vậy, có tồn tại dẫn xuất A ⇒ G α Þ * G w, trong đó α Þ * w liên quan đến các dẫn xuất ε từ 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)

Xét A ⇒ G’’ X 1 X 2 ... X n ⇒ i - 1 G’’ w. Phải có luật sinh A → β trong P sao cho X 1 X 2 ... X n tìm được khi loại bỏ các biến rỗng của β . Vậy A Þ * G X 1 X 2 ...X n (chứng minh tương tự như ở trên). Ta viết w = w 1 w 2 ...w n sao cho ∀ j ta có X j ⇒ * G’’ w j (bằng ít hơn i bước). Theo giả thiết quy nạp X j ⇒ * G’’ w j nếu X j là biến. Nếu X j là ký hiệu kết thúc thì w j = X j và X j ⇒ * G w j là hiển nhiên. Vậy A ⇒ * G w.

Cuối cùng ta áp dụng bổ đề 2 vào G’’ ta thu được G’ không có ký hiệu vô ích. Vì bổ đề 1 và bổ đề 2 không đưa ra thêm luật sinh mới nào nên G’ không có chứa ký hiệu là biến rỗng hay ký hiệu vô ích.

Hơn nữa S ⇒ * G’ w nếu và chỉ nếu S ⇒ * G w. Vậy L(G’) = L(G) - { ε }.

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

S ® AB

A ® aA | e

B ® bB | e

Trước hết, ta xác định tập các biến rỗng trong văn phạm: A, B là các biến rỗng vì có các luật sinh A ® e và B ® e. S cũng là biến rỗng vì có luật sinh S ® AB với A, B đều là các biến rỗng.

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

Theo quy tắc xây dựng tập luật sinh P’ trong định lý , ta có tập luật sinh mới như sau :

S ® AB | A | B

A ® aA | a

B ® bB | b

Lưu ý rằng văn phạm mới G’ không sản sinh ra ε, trong khi G lại có sinh ra từ rỗng e. Vậy muốn có một văn phạm thực sự tương đương với văn phạm G thì ta phải bổ sung thêm luật sinh S ® e vào tập luật sinh của G’. Ta có, văn phạm G’ tương đương G.

Luật sinh đơn vị

Một luật sinh có dạng A ® B với A, B đều là biến gọi là luật sinh đơn vị.

ĐỊNH LÝ 5.4 : Mỗi CFL không chứa e được sinh ra bởi CFG không có ký hiệu vô ích, luật sinh e hoặc luật sinh đơn vị .

Chứng minh

Đặt L là CFL không chứa e và L = L(G) với G (V, T, P, S) là một CFG nào đó.

Theo định lý 3 ta có thể giả sử G không có luật sinh e. 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ó luật sinh đơn vị dạng A ⇒^* B với A, B ∈ V 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 e và nếu A ⇒ G B 1 ⇒ G B 2 ... ⇒ G B m ⇒ 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 ⇒ * G B, 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’ (V, 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 các ký hiệu 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’).

Việc áp dụng bổ đề 1, bổ đề 2 để loại các ký hiệu vô ích không đưa ra thêm luật sinh nào chứng tỏ G không chứa ký hiệu vô ích.

Vậy, kết quả ta được một văn phạm thỏa điều kiện định lý.

Thí dụ 5.11 : 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

Gọi tập Δ_A = {B | A ⇒ * B}, xét các biến trong văn phạm, ta có :

Δ _E = { E, T, F } Δ _T = { T, F } Δ _F = { F }

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 :

E ® E + T | T * F | ( E ) | a

T ® T * F | ( E ) | a

F ® ( E ) | a