Tôi đang cố gắng để chứng minh những điều sau đây:Làm thế nào tôi có thể chứng minh rằng các dẫn xuất trong Chomsky Normal Form yêu cầu 2n - 1 bước?
Nếu G là một bối cảnh miễn phí Grammar in dạng chuẩn Chomsky, sau đó cho bất kỳ chuỗi w thuộc L (G) có độ dài n ≥ 1, nó đòi hỏi chính xác 2n -1 bước để làm cho bất kỳ dẫn xuất của w.
Tôi làm cách nào để chứng minh điều này?
Như một gợi ý - vì mỗi sản xuất trong Chomsky Normal Form hoặc có dạng
S → AB, cho thuộc đầu cuối A và B, hoặc các hình thức
S → x, cho thiết bị đầu cuối x,
sau đó phát sinh một chuỗi sẽ làm việc theo cách sau:
Áp dụng sản phẩm của biểu mẫu đầu tiên sẽ tăng số lượng nonterminals từ k lên k + 1, vì bạn thay thế một nonterminal (-1) bằng hai nonterminals (+2) để đạt được lợi nhuận ròng +1 nonterminal. Kể từ khi bắt đầu với một nonterminal, điều này có nghĩa là bạn cần phải làm n - 1 sản xuất của hình thức đầu tiên. Sau đó, bạn cần thêm n biểu mẫu thứ hai để chuyển đổi nonterminals thành thiết bị đầu cuối, cho tổng số n + (n - 1) = 2n - 1 sản phẩm.
Để cho thấy rằng bạn cần chính xác nhiều điều này, tôi khuyên bạn nên làm bằng chứng bằng mâu thuẫn và cho thấy bạn không thể làm điều đó với bất kỳ chi tiết nào hoặc ít hơn. Như một gợi ý, hãy thử đếm số lượng sản phẩm của từng loại được tạo ra và cho thấy rằng nếu nó không phải là 2n - 1, hoặc là chuỗi quá ngắn, hoặc bạn vẫn sẽ có số không còn lại.
Hy vọng điều này sẽ hữu ích!
: Bạn có thể cho biết lý do tại sao chúng ta cần phải thực hiện các sản phẩm n-1 của biểu mẫu đầu tiên. – justin
Chắc chắn! Mỗi thiết bị đầu cuối trong chuỗi kết quả cuối cùng được hình thành bằng cách lấy một nonterminal và mở rộng nó đến một thiết bị đầu cuối thông qua một số sản xuất của mẫu A -> a. Điều này có nghĩa rằng có, tại một số điểm, có tổng số n nonterminals sản xuất. Một trong số đó xuất phát miễn phí từ biểu tượng bắt đầu. Mỗi khi bạn thực hiện một sản xuất của các hình thức A -> BC, bạn sẽ có thêm một nonterminal. Do đó, bạn cần phải thực hiện các sản phẩm n-1 của mẫu A -> BC để bạn có thể tạo các nonterminals bổ sung cần thiết n-1. – templatetypedef
: Oh bạn có ý nói rằng '-1' của cụm từ 'n-1' xuất phát từ khi một trong số chúng xuất hiện miễn phí từ biểu tượng bắt đầu? – justin