Chuyển ngữ pháp thành Chomsky Normal Form?

Question

Chuyển ngữ pháp dưới đây thành Biểu mẫu bình thường Chomsky. Cung cấp tất cả các bước trung gian.

S -> AB | aB 
A -> aab|lambda 
B -> bbA 

Ok do đó, điều đầu tiên tôi làm là thêm một biến khởi đầu mới S0

vì vậy bây giờ tôi có

S0 -> S 
S -> AB | aB 
A -> aab|lambda 
B -> bbA 

sau đó tôi loại bỏ tất cả các quy tắc lambda:

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

Sau đó, tôi đã kiểm tra S->S và A->B loại các quy tắc không tồn tại. Và đó là câu trả lời tôi đưa ra, tôi có cần phải làm gì thêm hay tôi đã làm gì sai?

Answer 1

Wikipedia nói:

Trong khoa học máy tính, một ngữ pháp ngữ cảnh miễn phí được cho là trong hình thức bình thường Chomsky nếu tất cả các quy tắc sản xuất của nó có dạng:

• Một ->BC, hoặc
• Một -> α, hoặc
• S -> ε

nơi Một, B, C là biểu tượng không thuộc đầu cuối, α là một biểu tượng thiết bị đầu cuối, S là biểu tượng bắt đầu, và ε là chuỗi rỗng. Ngoài ra, không phải B cũng không C có thể là biểu tượng bắt đầu.

Tiếp tục công việc của bạn:

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

Thay vì sử dụng | để biểu thị sự lựa chọn khác nhau, chia một quy tắc thành nhiều quy tắc.

S0 -> S 
S -> AB 
S -> aB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 

Tạo quy tắc mới Y -> a và Z -> b bởi vì chúng tôi sẽ cần đến chúng sớm.

S0 -> S 
S -> AB 
S -> aB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 
Y -> a 
Z -> b 

S -> aB không có dạng S -> BC vì a là một thiết bị đầu cuối.Vì vậy, thay đổi a vào Y:

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 
Y -> a 
Z -> b 

Làm tương tự cho các B -> bb quy tắc:

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> aab 
B -> bbA 
B -> ZZ 
Y -> a 
Z -> b 

Đối A -> aab, tạo C -> YY; cho B -> bbA, tạo D -> ZZ:

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

Đối S -> B, lặp lại trong một quy tắc nơi S xảy ra ở phía bên tay phải và nội tuyến các quy tắc:

S0 -> B 
S0 -> S 
S -> AB 
S -> YB 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

Deal với các quy tắc S0 -> B và S0 -> S bằng cách tham gia bên tay phải sang bên trái Mặt khác của các quy tắc khác. Ngoài ra, xóa các quy tắc mồ côi (nơi biểu tượng LHS không bao giờ được sử dụng trên RHS):

S0 -> DA 
S0 -> ZZ 
S0 -> AB 
S0 -> YB 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

Và chúng ta đã hoàn tất. Phew!

Answer 2

câu trả lời khác: Ngữ pháp chỉ có thể sản xuất một số hữu hạn các chuỗi, cụ thể là 6.

S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb. 

Bạn bây giờ có thể ngưng tụ lại này để Chomsky Normal Form bằng tay.

---

Bằng cách thay thế, chúng tôi có thể tìm thấy tập hợp tất cả các chuỗi được tạo. quy tắc ban đầu của bạn:

S -> AB | aB. 
A -> aab | lambda. 
B -> bbA. 

Đầu tiên chia ra các S quy tắc:

S -> AB. 
S -> aB. 

Bây giờ thay thế những gì A và B mở rộng sang:

S -> AB 
    -> (aab | lambda) bbA 
    -> (aab | lambda) bb (aab | lambda). 
S -> aB 
    -> abbA 
    -> abb (aab | lambda). 

Mở rộng những một lần nữa để có được:

S -> aabbbaab. 
S -> aabbb. 
S -> bbaab. 
S -> bb. 
S -> abbaab. 
S -> abb. 

---

Để thay đổi tập hợp hữu hạn này thành Biểu mẫu thông thường Chomsky, nó đủ để làm điều đó bằng vũ lực mà không có bất kỳ sự bao thanh thông minh nào. Đầu tiên chúng tôi giới thiệu hai quy tắc thiết bị đầu cuối:

X -> a. 
Y -> b. 

Bây giờ cho mỗi chuỗi, chúng ta tiêu thụ chữ cái đầu tiên với một biến thiết bị đầu cuối và các chữ cái còn lại với một biến mới. Ví dụ: như thế này:

S -> aabbb. (initial rule, not in Chomsky Normal Form) 

S -> XC, where X->a and C->abbb. 
C -> XD, where X->a and D->bbb. 
D -> YE, where Y->b and E->bb. 
E -> YY, where Y->b and Y->b. 

Chúng tôi chỉ thực hiện quy trình này cho tất cả 6 chuỗi, tạo ra nhiều biến trung gian mới.

Answer 3

Nếu không có quá nhiều lý thuyết và chứng minh (bạn có thể xem điều này trong Wikipedia), có một vài điều bạn phải làm khi chuyển ngữ pháp ngữ pháp sang Chomsky Normal Form, bạn thường phải thực hiện bốn biểu mẫu bình thường Biến đổi. Đầu tiên, bạn cần xác định tất cả các biến có thể sinh ra chuỗi rỗng (lambda/epsilon), trực tiếp hoặc gián tiếp - (dạng Lambda-Free). Thứ hai, bạn cần phải loại bỏ các sản phẩm đơn vị - (dạng đơn vị miễn phí). Thứ ba, bạn cần phải tìm tất cả các biến được sống/hữu ích (hữu ích). Bốn, bạn cần phải tìm tất cả các ký hiệu có thể truy cập (Reachable). Ở mỗi bước bạn có thể hoặc không có ngữ pháp mới. Vì vậy, đối với vấn đề của bạn này là những gì tôi đã đưa ra ...

---

Context-Free Grammar

G(Variables = { A B S } 
Start = S 
Alphabet = { a b lamda} 

Production Rules = { 
S -> | AB | aB | 
A -> | aab | lamda | 
B -> | bbA | }) 

Remove lambda/epsilon

ERRASABLE(G) = { A } 

G(Variables = { A S B } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | B | 
B -> | bbA | bb | }) 

Remove đơn vị produtions

UNIT(A) { A } 
UNIT(B) { B } 
UNIT(S) { B S } 
G (Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Xác định biểu tượng trực tiếp s

LIVE(G) = { b A B S a } 

G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Di unreachable

REACHABLE (G) = { b A B S a } 
G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Thay thế tất cả các chuỗi hỗn hợp với không thuộc đầu cuối rắn

G(Variables = { A S B R I } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IIA | 
A -> | RRI | 
B -> | IIA | II | 
R -> | a | 
I -> | b | }) 

Chomsky Normal Form

G(Variables = { V A B S R L I Z } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IV | 
A -> | RL | 
B -> | IZ | II | 
R -> | a | 
I -> | b | 
L -> | RI | 
Z -> | IA | 
V -> | IA | })