Bài giảng lý thuyết ôtômát và ngôn ngữ hình thức: Chương 6 (mới nhất)

Chương 6 Đơn giản hóa VPPNC và các dạng chuẩn

6.1 Các phương pháp để biến đổi văn phạm 6.2 Hai dạng chuẩn quan trọng 6.3 Giải thuật thành viên cho văn phạm phi ngữ cảnh

Trang 189 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Các phương pháp để biến đổi văn phạm

(cid:132) Chuỗi trống đóng một vai trò khá đặc biệt trong nhiều định lý và chứng minh, và thường cần có một sự chú ý đặc biệt cho nó.

(cid:132) Nếu L ∋ λ thì biểu diễn L = L1 ∪ λ với L1 = L - λ. Nếu

G1 = (V1, T, S1, P1)

là văn phạm biểu diễn cho L1 thì

G = (V1 ∪ {S}, T, S, P1 ∪ {S → S1 | λ})

(cid:132) Trong chương này, chúng ta chỉ xem xét các NNPNC không

là văn phạm biểu diễn cho L.

(cid:132) Tuy nhiên những kết luận cho ngôn ngữ không chứa λ vẫn có

chứa λ.

Trang 190 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

thể áp dụng cho ngôn ngữ có chứa λ.

Một vài qui tắc thay thế hiệu quả

(cid:132) Định lý 6.1

(cid:132) Cho G = (V, T, S, P) là một VPPNC. Giả sử P có chứa luật sinh A → x1Bx2 trong đó A, B là các biến khác nhau và

B → y1 | y2 | ... | yn

là tập tất cả các luật sinh trong P mà có B ở vế trái. Cho G1= (V, T, S, P1) là VP được xây dựng bằng cách xóa đi

A → x1Bx2

từ P, và thêm vào nó

A → x1y1x2 | x1y2x2| ... | x1ynx2

Thì

Trang 191 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

L(G) = L(G1)

Ví dụ

(cid:132) Xét văn phạm G = ({A, B}, {a, b}, A, P) với các luật sinh

A → a | aA | bBc, B → abA | b.

Sau khi thay thế biến B ta nhận được VP tương đương như sau

(cid:132) Chú ý rằng, biến B và các luật sinh của nó vẫn còn ở trong VP mặc dù chúng không còn đóng vai trò gì trong bất kỳ dẫn xuất nào. Sau này chúng ta sẽ thấy rằng những luật sinh không cần thiết như vậy có thể bị loại bỏ ra khỏi văn phạm.

Trang 192 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

A → a | aA | babAc | bbc, B → abA | b (cid:132) Chuỗi abbc có các dẫn xuất trong G và G1 lần lượt như sau: A ⇒ aA ⇒ abBc ⇒ abbc A ⇒ aA ⇒ abbc

Loại bỏ đệ qui trái

(cid:132) Định lý 6.2 (Loại bỏ đệ qui trái)

(cid:132) Cho G = (V, T, S, P) là một VPPNC. Chia tập các luật sinh mà vế trái của chúng là một biến đã cho nào đó (chẳng hạn là A), thành hai tập con riêng biệt

(6.2) (6.3) A → Ax1 | Ax2 | ... | Axn A → y1 | y2 | ... | ym

với xi, yi ∈ (V ∪ T)*, và A không là prefix của bất kỳ yi nào. Xét G1 = (V ∪ {Z}, T, S, P1), trong đó Z ∉ V và P1 nhận được bằng cách thay mọi luật sinh của P có dạng (6.2 ) và (6.3) bởi A → yi | yiZ, i = 1, 2, . . . , m, Z → xi | xiZ, i = 1, 2, . . . , n,

Thì

Trang 193 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

L(G) = L(G1).

Loại bỏ đệ qui trái (tt)

(cid:132) Chứng minh

(cid:132) Các dạng câu mà A sinh ra trong văn phạm G có dạng:

*⇒

A A(x1 + x2 + ... + xn)* ⇒ yi(x1 + x2 + ... + xn)*

*⇒

Các dạng câu này cũng có thể được sinh ra trong G1 bằng cách chú ý Z có thể sinh ra các dạng câu có dạng

*⇒

Z (x1 + x2 + ... + xn)(x1 + x2 + ... + xn)*

yi(x1 + x2 + ... + xn)*

(cid:132) Ghi chú

(cid:132) Các luật sinh đệ qui-trái chỉ là một trường hợp đặc biệt của đệ

mà A → yi | yiZ nên A Vì vậy L(G) = L(G1).

(cid:132) Một văn phạm được gọi là đệ qui-trái nếu có một biến A nào đó

qui-trái trong văn phạm như được phát biểu sau.

*⇒

mà đối với nó A

Ax là có thể. Trang 194 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ

(cid:132) Sử dụng Định lý 6.2 để loại bỏ các luật sinh đệ qui-trái khỏi VP

(cid:132) Áp dụng định lý cho biến A ta được tập luật sinh mới như sau:

A → Aa | aBc | λ B → Bb | ba

B → Bb | ba

(cid:132) Áp dụng định lý một lần nữa lần này cho biến B ta được tập

A → aBc | λ | aBcZ | Z Z → a | aZ

luật sinh kết quả cuối cùng như sau:

(cid:132) Nhận xét

(cid:132) Việc loại bỏ các luật sinh đệ qui-trái đưa ra các biến mới. VP

A → aBc | aBcZ | Z | λ Z → a | aZ B → ba | baY Y → b | bY

Trang 195 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

kết quả có thể là "đơn giản" hơn đáng kể so với VP gốc nhưng một cách tổng quát nó sẽ có nhiều biến và luật sinh hơn.

Luật sinh vô dụng

(cid:132) Định nghĩa 6.1:

w, S

*⇒

(cid:132) Cho G = (V, T, S, P) là một VPPNC. Một biến A ∈ V được gọi là khả dụng nếu và chỉ nếu có ít nhất một chuỗi w ∈ L(G) sao xAy cho với x, y ∈ (V ∪ T)*. Bằng lời, một biến là khả dụng nếu và chỉ nếu nó xuất hiện trong ít nhất một dẫn xuất. Một biến mà không khả dụng thì gọi là vô dụng. Một luật sinh được gọi là vô dụng nếu nó có chứa bất kỳ biến vô dụng nào.

(cid:132) Các dạng vô dụng (cid:132) Vô dụng loại 1: A (cid:132) Vô dụng loại 2: S

w ∈ T* xAy

⇒ ⇒

Trang 196 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Loại bỏ các luật sinh vô dụng

(cid:132) Định lý 6.3

(cid:132) Cho G = (V, T, S, P) là một VPPNC, ∃ một VP tương đương G0

(cid:132) Chứng minh

(cid:132) Loại bỏ các biến và luật sinh vô dụng loại 1

= (V0, T, S, P0) mà không chứa bất kỳ biến vô dụng nào.

Tạo văn phạm G1 = (V1, T, S, P1) với V1 là tập biến không vô dụng loại 1. Ta tìm V1 như sau: 1. Khởi tạo V1 = ∅. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm

vào V1. (cid:132) Đối với mỗi A ∈ V mà có luật sinh A → x, x ∈ (V1∪T)*,

thì thêm A vào V1.

Trang 197 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

3. Loại khỏi P các luật sinh có chứa các biến ∉ V1, ta được P1.

Loại bỏ các luật sinh vô dụng (tt)

(cid:132) Để loại tiếp các biến và các luật sinh vô dụng loại 2 ta dựa vào G1 vừa có ở trên và vẽ đồ thị phụ thuộc cho nó, sau đó tìm tập các biến không đạt tới được từ S. Loại các biến này và các luật sinh liên quan đến nó ra khỏi G1 ta được văn phạm kết quả G0.

(cid:132) Đồ thị phụ thuộc (dependency graph)

(cid:132) Là một đồ thị có các đỉnh biểu diễn các biến, còn một cạnh nối

hai đỉnh A và B khi và chỉ khi có luật sinh dạng

(cid:132) Ví dụ

(cid:132) Loại bỏ các biến và các luật sinh vô dụng ra khỏi văn phạm

A → xBy A B

G = ({S, A, B, C}, {a, b}, S, P), với tập luật sinh P là:

Trang 198 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S → aS | A | C A → a B → aa C → aCb

Ví dụ

(cid:132) Loại bỏ các biến vô dụng loại 1 ta được

S → aS | A | C A → a B → aa C → aCb

(cid:132) Loại bỏ các biến vô dụng loại 2 ta được

V1 = {S, A, B} và tập luật sinh P1 S → aS | A A → a B → aa

S A B

văn phạm kết quả

(cid:132) Nhận xét

(cid:132) Nếu thay đổi thứ tự loại bỏ (loại bỏ các biến và luật sinh vô

S → aS | A A → a

Trang 199 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

dụng loại 2 trước) thì sẽ không loại bỏ được tất cả các biến và luật sinh vô dụng chỉ bằng một lần như ví dụ sau cho thấy.

Ví dụ (tt)

(cid:132) Xét văn phạm sau

(cid:132) Nếu loại bỏ các biến và luật sinh vô dụng loại 2 trước ta thấy

S → aSb | ab | A A → aAB B → b

văn phạm vẫn không thay đổi vì tất cả các biến đều đạt tới được từ S. Sau đó loại bỏ tiếp các biến và luật sinh vô dụng loại 1 ta sẽ được văn phạm sau:

Trang 200 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S → aSb | ab | A B → b (cid:132) Rõ ràng văn phạm này còn biến B là vô dụng loại 2.

Loại bỏ luật sinh-λ

(cid:132) Định nghĩa 6.2

(cid:132) Bất kỳ luật sinh nào của VPPNC có dạng

A → λ

được gọi là luật sinh-λ. Bất kỳ biến A nào mà

A λ

*⇒

(cid:132) là có thể thì được gọi là khả trống (nullable).

(cid:132) Định lý 6.4

(cid:132) Cho G là một VPPNC bất kỳ mà L(G) không chứa λ, thì tồn tại một văn phạm G0 tương đương mà không có chứa luật sinh-λ.

(cid:132) Chứng minh: Bước 1 (cid:132) Tìm tập VN tất cả các biến khả trống của G bằng các bước sau.

Trang 201 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Loại bỏ luật sinh-λ

1. Đối với mọi luật sinh A → λ, đưa A vào VN. 2. Lặp lại bước sau cho đến khi không còn biến nào được thêm

vào VN. (cid:132) Đối với mọi luật sinh B → A1A2 … An, mà A1, A2, An ∈ VN

thì đặt B vào VN.

Trang 202 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Bước 2 (cid:132) Sau khi có tập VN ta xây dựng tập luật sinh như sau. (cid:132) Ứng với mỗi luật sinh có dạng A → x1x2 … xm, m ≥ 1, trong đó mỗi xi ∈ V ∪ T, đặt luật sinh này vào cùng với các luật sinh được sinh ra bằng cách thay thế các biến khả trống bằng λ trong mọi tổ hợp có thể, ngoại trừ nếu tất cả các xi đều khả trống thì không đặt luật sinh A → λ vào P0 của G0

Ví dụ

(cid:132) Loại bỏ các luật sinh-λ của văn phạm sau: C → D | λ D → d

(cid:132) Vì B → λ và C → λ suy ra B và C là các biến khả trống. (cid:132) Vì A → BC nên suy ra A cũng là biến khả trống. Ngoài ra

S → ABaC A → BC B → b | λ

(cid:132) Theo Bước 2 ta xây dựng được tập luật sinh mới tương đương

không còn biến nào khác là khả trống.

như sau:

Trang 203 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S → ABaC | BaC | AaC | Aba | aC | Aa | Ba | a A → BC | B | C B → b C → D D → d

Loại bỏ luật sinh đơn vị

(cid:132) Định nghĩa 6.3

(cid:132) Bất kỳ luật sinh nào của VPPNC có dạng

A → B

(cid:132) Định lý 6.5

(cid:132) Cho G = (V, T, S, P) là một VPPNC bất kỳ không có luật sinh- λ, thì tồn tại một VPPNC G1 = (V1, T, S, P1) mà không có bất kỳ luật sinh đơn vị nào và tương đương với G1.

(cid:132) Chứng minh

trong đó A, B ∈ V được gọi là luật sinh-đơn vị.

(cid:132) Điều này thực hiện bằng cách vẽ đồ thị phụ thuộc cho G nhưng một cạnh nối 2 đỉnh A và B khi và chỉ khi có luật sinh-đơn vị A → B. Hai biến A và B thõa (*) khi và chỉ khi có một con đường trong đồ thị đi từ A đến B.

Trang 204 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

⇒* 1. Đặt vào trong P1 tất cả các luật sinh không đơn vị của P. 2. Đối với mỗi biến A tìm tất cả các biến B mà A B (*)

Ví dụ

3. Đối với mỗi A, B thõa (*) thêm vào trong P1 các luật sinh

(cid:132) Ví dụ

(cid:132) Loại bỏ các luật sinh đơn vị

A → y1 | y2 | ... | yn với B → y1 | y2 | ... | yn là các luật sinh không đơn vị của B.

Trước hết, đặt các luật sinh không đơn vị vào trong P1 cho VP sau

S → Aa A → a | bc B → bb S → Aa | B B → A | bb A → a | bc | B

Từ ĐTPT ta đưa được thêm các luật sinh sau vào

S A B

Trang 205 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S → a | bc | bb A → bb B → a | bc

Ví dụ (tt)

(cid:132) Kết quả ta có văn phạm tương đương sau không có luật sinh

đơn vị

(cid:132) Định lý 6.6

(cid:132) Cho L là một NNPNC không chứa λ, tồn tại một VPPNC sinh ra L mà không chứa bất kỳ luật sinh vô dụng, luật sinh-λ, hay luật sinh-đơn vị nào.

(cid:132) Chứng minh:

S → Aa | a | bc | bb A → a | bc | bb B → bb | a | bc

Trang 206 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

B1. Loại bỏ luật sinh-λ B2. Loại bỏ luật sinh đơn vị B3. Loại bỏ luật sinh vô dụng loại 1, rồi vô dụng loại 2

Một số nhận xét

1. Loại bỏ biến vô dụng loại 1 có thể sinh ra biến vô dụng loại 2. 2. Việc loại bỏ biến vô dụng loại 2 không sinh ra biến vô dụng

loại 1.

3. Văn phạm không có luật sinh đơn vị thì việc loại bỏ luật sinh-λ

có thể sinh ra luật sinh-đơn vị.

4. Văn phạm không có luật sinh-λ thì việc loại bỏ luật sinh-đơn vị

không thể sinh ra luật sinh-λ mới.

Trang 207 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

5. Loại bỏ luật sinh-λ có thể sinh ra biến vô dụng loại 1. 6. Loại bỏ luật sinh-đơn vị có thể sinh ra biến vô dụng loại 2. 7. Văn phạm không có luật sinh-λ, luật sinh-đơn vị thì việc loại bỏ các luật sinh vô dụng loại 1, loại 2 không sinh ra thêm bất kỳ luật sinh-λ và luật sinh-đơn vị nào mới.

Dạng chuẩn Chomsky

(cid:132) Định nghĩa 6.4

(cid:132) Một VPPNC là thuộc dạng chuẩn Chomsky nếu mọi luật sinh

có dạng

A → BC, hoặc A → a

(cid:132) Định lý 6.7

(cid:132) Bất kỳ VPPNC G = (V, T, S, P) nào với λ ∉ L(G) đều có một văn phạm tương đương G1 = (V1, T, S, P1) có dạng chuẩn Chomsky. (cid:132) Chứng minh

(cid:132) Không mất tổng quát giả sử G không có luật sinh-vô dụng, luật sinh-đơn vị và luật sinh-λ. Ta xây dựng văn phạm G1 có dạng chuẩn Chomsky bằng thủ tục sau:

Trang 208 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

trong đó A, B, C ∈ V, còn a ∈ T.

Thủ tục: G-to-GChomsky

(cid:132) Input: G = (V, T, S, P) với λ ∉ L(G) (cid:132) Output: G1 = (V1, T, S, P1) có dạng chuẩn Chomsky. 1. Đặt các luật sinh A → a vào P1. 2. Đối với các luật sinh A → x1x2 ... xn với n ≥ 2, xi ∈ (V ∪ T) thì thay các kí hiệu kết thúc, chẳng hạn xk = a, bằng các biến đại diện mới Ba, tạo thành các luật sinh trung gian A → C1C2...Cn. 3. Ứng với mỗi biến đại diện Ba đặt vào P1 các luật sinh Ba → a. 4. Sau khi thực hiện bước 2, ứng với mỗi luật sinh A → C1C2 ...

Trang 209 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Cn mà n = 2 đặt nó vào P1. Ngược lại ứng với n > 2 ta giới thiệu các biến mới D1, D2, ... và đưa vào các luật sinh sau: A → C1D1 D1 → D1D2 M Dn-2 → Cn-1Cn

Ví dụ

c 1

ớ

S → a B → b

B

c 4

ớ

B

(cid:132) Hãy biến đổi VP sau thành VP có dạng chuẩn Chomsky. S → AD1 D1 → BXa A → XaD2 D2 → XaXb

Bước 2

ước 3

S → a | ABa A → aab B → b | Ac S → ABXa A → XaXaXb B → AXc

Kết quả

Xa → a Xb → b Xc → c

Trang 210 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S → a | AD1 D1 → BXa A → XaD2 D2 → XaXb B → b | AXc Xa → a Xb → b Xc → c

Dạng chuẩn Greibach

(cid:132) Định nghĩa 6.5

(cid:132) Một VPPNC là thuộc dạng chuẩn Greibach nếu mọi luật sinh

có dạng

A → ax

(cid:132) Định lý 6.8

(cid:132) Đối với mọi VPPNC G với λ ∉ L(G), thì tồn tại một văn phạm

trong đó a ∈ T còn x ∈ V*.

(cid:132) Chứng minh

(cid:132) Không mất tính tổng quát giả sử G không có luật sinh-vô dụng, luật sinh-đơn vị và luật sinh-λ. Ta xây dựng văn phạm có dạng chuẩn Greibach bằng thủ tục sau.

Trang 211 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

tương đương trong dạng chuẩn Greibach.

Thủ tục: G-to-GGreibach

(cid:132) Input: G = (V, T, S, P) với λ ∉ L(G) (cid:132) Output: G1 = (V1, T, S, P1) có dạng chuẩn Greibach. 1. Đánh số thứ tự cho các biến chẳng hạn là A1, A2, . . . An. 2. Dùng Định lý 6.1 và 6.2 để viết lại VP sao cho các luật sinh có

một trong ba dạng sau a ∈ T và xi ∈ (V ∪ T)*

(cid:132) Điều này thực hiện được bằng cách sử dụng Định lý 6.1 và 6.2

Zi là các biến mới Ai → Ajxj, i < j Zi → Ajxj, j ≤ n Ai → axi

(cid:132) Giả sử xét luật sinh của biến Ai. Nếu có luật sinh Ai → Ajx mà i > j thì thay Aj đi đầu bằng các vế phải của nó, và làm cho đến khi các luật sinh của Ai có dạng Ai → Ajx, i ≤ j. Đến đây loại đệ qui trái cho Ai thì các luật sinh của nó sẽ có dạng như đã nêu.

Trang 212 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

cho các biến Ai theo thứ tự i đi từ 1, 2, ... đến n như sau.

Thủ tục: G-to-GGreibach (tt)

(cid:132) Thay An đi đầu vế phải của các luật sinh bằng các vế phải của

dạng 3. Sau khi thực hiện bước 2, tất cả các luật sinh của An phải có An → axn

nó. Kết quả các luật sinh của An-1 có dạng

An-1 → axn-1 (cid:132) Tương tự thay thế An-1 đi đầu vế phải của các luật sinh bằng

các vế phải của nó. Và thực hiện lần lượt cho đến A1.

(cid:132) Ví dụ

(cid:132) Biến đổi VP sau thành VP có dạng chuẩn Greibach

4. Thay các kí hiệu kết thúc, chẳng hạn a, không đi đầu vế phải bằng các biến đại diện, chẳng hạn Xa, đồng thời thêm vào các luật sinh mới Xa → a.

S → SBb | Ab A → Sb | Ba B → Sb | a Trang 213 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Ví dụ

S → SBb | Ab A → Sb | Ba B → Sb | a

Loại đệ qui trái

S0 → S0B2b | A1b

(1) (2) S0 → A1b | A1bZ0 Z0 → B2b | B2bZ0

Thay thế

A1 → S0b | B2a A1 → A1bb | A1bZ0b | B2a

Loại đệ qui trái

A1 → B2a | B2aZ1 (3) Z1 → bb | bZ0b | bbZ1 | bZ0bZ1 (4)

Thay thế

B2 → S0b | a

B2 → A1ba | A1bZ0a | b Thay thế

(5)

B2aZ1bZ0a | b

Trang 214 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

aZ1bZ0a | abaZ2 | aZ1baZ2 | abZ0aZ2 | aZ1bZ0aZ2 (6) Loại đệ qui trái

Ví dụ (tt)

(5) B2 → b | bZ3

Thay thế

A1 → B2a | B2aZ1 (3) A1 → ba | bZ2a | baZ1 |bZ2aZ1 (7)

Thay thế

S0 → A1b | A1bZ0 (1) S0 → bab | bZ2ab | baZ1b |

bZ2aZ1b | babZ0 | bZ2abZ0 | (8) baZ1bZ0 | bZ2aZ1bZ0

Thay thế

Trang 215 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Z0 → B2b | B2bZ0 (2) Z0 → bb | bZ2b | bbZ0 |bZ2bZ0 (9)

Ví dụ (tt)

Văn phạm gần- Greibach

Trang 216 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

Thay kí hiệu kết thúc không đi đầu bằng biến đại diện

Giải thuật thành viên cho VPPNC

(cid:132) Giải thuật CYK (J.Cocke, D.H.Younger, T.Kasami)

(cid:132) Input: Văn phạm Chomsky G = (V, T, S, P)

Chuỗi w = a1a2 … an (cid:132) Output: “Yes” + DXTN hoặc “No”. (cid:132) Chúng ta định nghĩa các chuỗi con

(cid:132) Và các tập con của V

*⇒

wij = ai ... aj,

(cid:132) Để ý w = w1n, vậy w ∈ L(G) khi và chỉ khi S ∈ V1n. (cid:132) Vậy để biết w có ∈L(G) hay không chúng ta tính V1n và xem S

Vij = {A ∈ V : A wij},

Trang 217 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

có ∈V1n hay không.

Giải thuật CYK

*⇒

*⇒ thời A → BC thì A

(cid:132) A ∈ Vii nếu và chỉ nếu A có luật sinh A → ai. (cid:132) Vậy, Vii có thể được tính ∀i, 1 ≤ i ≤ n. wik (⇔ B ∈ Vik), C (cid:132) Nếu B *⇒

w(k+1)j (⇔ C ∈ V(k+1)j) và đồng

(cid:132) Vij = ∪k∈{i, i+1, ... , j – 1}{A: A → BC, với B ∈ Vik, C ∈ V(k+1)j} (cid:132) Quá trình tính các tập Vij (cid:132) V11, V22, ...,Vnn (cid:132) V12, V23, . . .,V(n-1)n (cid:132) V13, V24, . . .,V(n-2)n (cid:132) ... (cid:132) V1n

Trang 218 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

wij (⇔ A ∈ Vij) ∀ i ≤ k, k < j.

Ví dụ

(cid:132) Sử dụng giải thuật CYK đê PTCP chuỗi w = aabbb trên G sau

(cid:132) Ta có w = a a b b b 1 2 3 4 5

(1) (2, 3) (4, 5) S → AB A → BB | a B → AB | b

(cid:132) V11 = {A}, V22 = {A}, V33 = {B}, V44 = {B}, V55 = {B}, (cid:132) V12 = ∅, V23 = {S, B}, V34 = {A}, V45 = {A}, (cid:132) V13 = {S, B}, V24 = {A}, V35 = {S, B}, (cid:132) V14 = {A}, V25 = {S, B}, (cid:132) V15 = {S, B}.

Trang 219 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin

S ∈ V15 ⇒ w ∈ L(G).