Văn phạm nào sau đây KHÔNG nhập nhằng:
Trả lời:
Đáp án đúng: B
Câu hỏi yêu cầu tìm văn phạm KHÔNG nhập nhằng.
* **Văn phạm nhập nhằng (Ambiguous Grammar):** Là văn phạm mà một chuỗi có thể có nhiều cây cú pháp (parse tree) khác nhau, hoặc có nhiều dẫn xuất bên trái (leftmost derivation) khác nhau.
Phân tích từng đáp án:
* **A. S→ aSb; S->bSa; S-> SS; S->a:** Văn phạm này nhập nhằng vì có thể tạo ra nhiều cây cú pháp cho cùng một chuỗi. Ví dụ, chuỗi "ababa" có thể được tạo ra bằng nhiều cách khác nhau sử dụng luật `S -> SS`.
* **B. S → aSbS; S->bSaS; S->a; S->epsilon:** Văn phạm này cũng nhập nhằng. Ví dụ, chuỗi "aa" có thể được dẫn xuất từ S -> aSaS -> a a hoặc một số cách khác.
* **C. S→aS; S->aSb; S->b:** Văn phạm này nhập nhằng. Ví dụ chuỗi `ab` có thể được tạo ra từ `S -> aS -> ab` hoặc `S -> aSb -> ab`. Thật ra văn phạm này sinh ra các chuỗi có dạng `a^n b^m` với n >= 1 và m <= 1.
* **D. S→ aS; S->bS; S->epsilon:** Văn phạm này KHÔNG nhập nhằng. Nó sinh ra các chuỗi các ký tự a và b bất kỳ theo thứ tự nào, bao gồm cả chuỗi rỗng. Mỗi chuỗi chỉ có một cây cú pháp duy nhất.
Vậy đáp án đúng là D.
