Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Chuỗi nào sau đây được sinh ra bởi G
Trả lời:
Đáp án đúng: D
Văn phạm G cho phép sinh ra các biểu thức với toán hạng là 'a' hoặc 'b', và các toán tử là '+' hoặc '*' áp dụng cho hai toán hạng liền kề.
* **Phương án A: a++b*** Không thể sinh ra vì có hai toán tử '+' liền nhau mà không có toán hạng ở giữa.
* **Phương án B: ab++a*** Không thể sinh ra vì có hai toán tử '+' liền nhau mà không có toán hạng ở giữa.
* **Phương án C: ab+ba*** Có thể sinh ra theo các bước sau:
1. E -> EE+ (Sử dụng luật E->EE+)
2. E -> aE+ (Sử dụng luật E->a)
3. E -> ab+ (Sử dụng luật E->b)
4. E -> EE* (Sử dụng luật E->EE*)
5. E -> (ab+)E* (Sử dụng luật E->EE+ ở bước 3)
6. E -> (ab+)b* (Sử dụng luật E->b)
7. E -> ab+ba* (Sử dụng luật E->a)
Vậy đáp án đúng là C