Đơn giản hóa CFG

Trong CFG, có thể xảy ra rằng tất cả các quy tắc sản xuất và ký hiệu không cần thiết cho việc lấy ra các chuỗi. Bên cạnh đó, có thể có một số sản phẩm rỗng và sản xuất đơn vị. Loại bỏ các sản phẩm và biểu tượng này được gọi làsimplification of CFGs. Đơn giản hóa về cơ bản bao gồm các bước sau:

Giảm CFG
Loại bỏ sản xuất đơn vị
Loại bỏ các sản phẩm vô hiệu

Giảm CFG

CFG được giảm theo hai giai đoạn -

Phase 1 - Bắt nguồn từ một ngữ pháp tương đương, G’, từ CFG, G, sao cho mỗi biến dẫn xuất một số chuỗi đầu cuối.

Derivation Procedure -

Bước 1 - Bao gồm tất cả các ký hiệu, W₁, dẫn xuất một số thiết bị đầu cuối và khởi tạo i=1.

Bước 2 - Bao gồm tất cả các ký hiệu, W_i+1, dẫn xuất W_i.

Bước 3 - Tăng dần i và lặp lại Bước 2, cho đến khi W_i+1 = W_i.

Bước 4 - Bao gồm tất cả các quy tắc sản xuất có W_i trong đó.

Phase 2 - Bắt nguồn từ một ngữ pháp tương đương, G”, từ CFG, G’, sao cho mỗi biểu tượng xuất hiện ở dạng thông tin.

Derivation Procedure -

Bước 1 - Bao gồm biểu tượng bắt đầu trong Y₁ và khởi tạo i = 1.

Bước 2 - Bao gồm tất cả các ký hiệu, Y_i+1, có thể bắt nguồn từ Y_i và bao gồm tất cả các quy tắc sản xuất đã được áp dụng.

Bước 3 - Tăng dần i và lặp lại Bước 2, cho đến khi Y_i+1 = Y_i.

Vấn đề

Tìm một văn phạm rút gọn tương đương với văn phạm G, có quy tắc sản xuất, P: S → AC | B, A → a, C → c | BC, E → aA | e

Giải pháp

Phase 1 -

T = {a, c, e}

W ₁ = {A, C, E} từ các quy tắc A → a, C → c và E → aA

W ₂ = {A, C, E} U {S} từ quy tắc S → AC

W ₃ = {A, C, E, S} Ư ∅

Vì W ₂ = W ₃ , chúng ta có thể suy ra G 'là -

G '= {{A, C, E, S}, {a, c, e}, P, {S}}

trong đó P: S → AC, A → a, C → c, E → aA | e

Phase 2 -

Y ₁ = {S}

Y ₂ = {S, A, C} từ quy tắc S → AC

Y ₃ = {S, A, C, a, c} từ các quy tắc A → a và C → c

Y ₄ = {S, A, C, a, c}

Vì Y ₃ = Y ₄ , chúng ta có thể suy ra G ”là -

G ”= {{A, C, S}, {a, c}, P, {S}}

trong đó P: S → AC, A → a, C → c

Loại bỏ sản xuất đơn vị

Bất kỳ quy tắc sản xuất nào ở dạng A → B trong đó A, B ∈ Không đầu cuối được gọi là unit production..

Thủ tục loại bỏ -

Step 1 - Để loại bỏ A → B, thêm sản xuất A → x quy tắc ngữ pháp bất cứ khi nào B → xxảy ra trong ngữ pháp. [x ∈ Terminal, x có thể là Null]

Step 2 - Xóa A → B từ ngữ pháp.

Step 3 - Lặp lại từ bước 1 cho đến khi loại bỏ tất cả các sản phẩm của đơn vị.

Problem

Xóa đơn vị sản xuất khỏi phần sau -

S → XY, X → a, Y → Z | b, Z → M, M → N, N → a

Solution -

Có 3 đơn vị sản xuất trong ngữ pháp -

Y → Z, Z → M và M → N

At first, we will remove M → N.

Khi N → a, chúng ta thêm M → a, và M → N bị loại bỏ.

Bộ sản xuất trở thành

S → XY, X → a, Y → Z | b, Z → M, M → a, N → a

Now we will remove Z → M.

Khi M → a, chúng ta thêm Z → a, và Z → M bị loại bỏ.

Bộ sản xuất trở thành

S → XY, X → a, Y → Z | b, Z → a, M → a, N → a

Now we will remove Y → Z.

Khi Z → a, chúng ta thêm Y → a, và Y → Z bị loại bỏ.

Bộ sản xuất trở thành

S → XY, X → a, Y → a | b, Z → a, M → a, N → a

Bây giờ Z, M và N không thể truy cập được, do đó chúng tôi có thể xóa chúng.

CFG cuối cùng là đơn vị sản xuất miễn phí -

S → XY, X → a, Y → a | b

Loại bỏ các sản phẩm vô hiệu

Trong CFG, một ký hiệu không phải đầu cuối ‘A’ là biến nullable nếu có sản xuất A → ε hoặc có một dẫn xuất bắt đầu từ A và cuối cùng kết thúc với

ε: A → .......… → ε

Thủ tục loại bỏ

Step 1 - Tìm ra các biến không đầu cuối có thể nullable mà suy ra ε.

Step 2 - Đối với mỗi lần sản xuất A → a, xây dựng tất cả các sản phẩm A → x Ở đâu x được lấy từ ‘a’ bằng cách xóa một hoặc nhiều thiết bị không phải thiết bị đầu cuối khỏi Bước 1.

Step 3 - Kết hợp các sản phẩm gốc với kết quả của bước 2 và loại bỏ ε - productions.

Problem

Xóa sản xuất rỗng khỏi phần sau -

S → ASA | aB | b, A → B, B → b | ∈

Solution -

Có hai biến nullable - A và B

At first, we will remove B → ε.

Sau khi loại bỏ B → ε, bộ sản xuất trở thành -

S → ASA | aB | b | a, A ε B | b | & epsilon, B → b

Now we will remove A → ε.

Sau khi loại bỏ A → ε, bộ sản xuất trở thành -

S → ASA | aB | b | a | SA | NHƯ | S, A → B | b, B → b