Chomsky Dạng bình thường
CFG ở dạng Chomsky Normal nếu Sản phẩm ở các dạng sau:
- A → a
- A → BC
- S → ε
trong đó A, B và C không phải là thiết bị đầu cuối và a là thiết bị đầu cuối.
Thuật toán chuyển đổi thành dạng chuẩn Chomsky -
Step 1 - Nếu ký hiệu bắt đầu S xảy ra ở một số bên phải, tạo một biểu tượng bắt đầu mới S’ và một sản xuất mới S’→ S.
Step 2- Loại bỏ các sản phẩm Null. (Sử dụng thuật toán loại bỏ sản xuất Null đã thảo luận trước đó)
Step 3- Loại bỏ các sản phẩm đơn vị. (Sử dụng thuật toán loại bỏ sản xuất đơn vị đã thảo luận trước đó)
Step 4 - Thay thế từng sản xuất A → B1…Bn Ở đâu n > 2 với A → B1C Ở đâu C → B2 …Bn. Lặp lại bước này cho tất cả các sản phẩm có hai hoặc nhiều ký hiệu ở phía bên phải.
Step 5 - Nếu mặt phải của bất kỳ sản xuất nào ở dạng A → aB nơi a là thiết bị đầu cuối và A, B không phải là thiết bị đầu cuối, sau đó sản xuất được thay thế bằng A → XB và X → a. Lặp lại bước này cho mọi sản xuất ở dạngA → aB.
Vấn đề
Chuyển đổi CFG sau thành CNF
S → ASA | aB, A → B | S, B → b | ε
Giải pháp
(1) Từ S xuất hiện trong RHS, chúng tôi thêm một trạng thái mới S0 và S0→S được thêm vào bộ sản xuất và nó trở thành -
S 0 → S, S → ASA | aB, A → B | S, B → b | ∈
(2) Bây giờ chúng tôi sẽ loại bỏ các sản phẩm rỗng -
B → ∈ và A → ∈
Sau khi loại bỏ B → ε, tập hợp sản xuất trở thành -
S 0 → S, S → ASA | aB | a, A → B | S | ∈, B → b
Sau khi loại bỏ A → ∈, tập hợp sản xuất trở thành -
S 0 → S, S → ASA | aB | a | NHƯ | SA | S, A → B | S, B → b
(3) Bây giờ chúng tôi sẽ loại bỏ các sản phẩm đơn vị.
Sau khi loại bỏ S → S, bộ sản xuất trở thành -
S 0 → S, S → ASA | aB | a | NHƯ | SA, A → B | S, B → b
Sau khi loại bỏ S 0 → S, bộ sản xuất trở thành -
S 0 → ASA | aB | a | NHƯ | SA, S → ASA | aB | a | NHƯ | SA
A → B | S, B → b
Sau khi loại bỏ A → B, tập hợp sản xuất trở thành -
S 0 → ASA | aB | a | NHƯ | SA, S → ASA | aB | a | NHƯ | SA
A → S | b
B → b
Sau khi loại bỏ A → S, tập hợp sản xuất trở thành -
S 0 → ASA | aB | a | NHƯ | SA, S → ASA | aB | a | NHƯ | SA
A → b | ASA | aB | a | NHƯ | SA, B → b
(4) Bây giờ chúng ta sẽ tìm ra nhiều hơn hai biến trong RHS
Ở đây, S 0 → ASA, S → ASA, A → ASA vi phạm hai Non-terminal trong RHS
Do đó, chúng tôi sẽ áp dụng bước 4 và bước 5 để có được bộ sản xuất cuối cùng sau đây trong CNF -
S 0 → AX | aB | a | NHƯ | SA
S → AX | aB | a | NHƯ | SA
A → b | AX | aB | a | NHƯ | SA
B → b
X → SA
(5)Chúng ta phải thay đổi quá trình sản xuất S 0 → aB, S → aB, A → aB
Và tập hợp sản xuất cuối cùng trở thành -
S 0 → AX | YB | a | NHƯ | SA
S → AX | YB | a | NHƯ | SA
A → b A → b | AX | YB | a | NHƯ | SA
B → b
X → SA
Y → a