Câu hỏi 13
Qui tắc thay thế được sử dụng để miêu tả cách viết lại một chữ cái bằng một chuỗi các chữ cái khác. Ví dụ, chúng ta có thể có hai quy tắc thay thế: A→BB và B→ABA. Tức là chữ cái A được thay bằng hai chữ cái B, một chữ cái B thay bằng ba chữ cái ABA.
Nếu ta bắt đầu từ chữ cái A và dùng các quy tắc thay thế A→BB và B→ABA, ta sẽ có: A→BB→ABAABA→BBABABBBBABABB sau 3 bước. Cần lưu ý rằng tại mỗi bước, tất cả các chữ cái trong dãy đều được thay thế theo quy tắc ở trên.
Hỏi bộ qui tắc thay thế nào có thể cho ra kết quả BAACCACCABAB?
Cách hiểu biên tập: câu hỏi về chuỗi đích mới không ấn định chữ khởi đầu; cần xét các quy tắc có thể sinh ra chuỗi đích hay không.
Nếu ta bắt đầu từ chữ cái A và dùng các quy tắc thay thế A→BB và B→ABA, ta sẽ có: A→BB→ABAABA→BBABABBBBABABB sau 3 bước. Cần lưu ý rằng tại mỗi bước, tất cả các chữ cái trong dãy đều được thay thế theo quy tắc ở trên.
Hỏi bộ qui tắc thay thế nào có thể cho ra kết quả BAACCACCABAB?
Cách hiểu biên tập: câu hỏi về chuỗi đích mới không ấn định chữ khởi đầu; cần xét các quy tắc có thể sinh ra chuỗi đích hay không.