Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt các sản xuất (1) (2) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm này của quá trình phân tích thì đầu đọc trên xâu vào đang trỏ tới kí tự nào?
Trả lời:
Đáp án đúng: D
Ta thực hiện phân tích xâu "aacbc" theo thuật toán Top-down và các luật sinh được chọn như sau:
1. **S -> aSbS**
- Xâu hiện tại: `aSbS`
2. **S -> aS**
- Xâu hiện tại: `a(aS)bS` tức là `aaSbS`
3. **S -> aS**
- Xâu hiện tại: `aa(aS)bS` tức là `aaaSbS`
4. **S -> c**
- Xâu hiện tại: `aa(c)bS` tức là `aacbS`
5. **S -> aSbS**
- Xâu hiện tại: `aacb(aSbS)` tức là `aacbaSbS`
6. **S -> aS**
- Xâu hiện tại: `aacba(aS)bS` tức là `aacbaaSbS`
7. **S -> c**
- Xâu hiện tại: `aacba(c)bS` tức là `aacbacbS`
Như vậy, sau 7 bước, ta có xâu `aacbacbS`. Khi so khớp với xâu vào `aacbc`, ta thấy `aacbacbS` khác với `aacbc`. Tuy nhiên, câu hỏi yêu cầu xác định vị trí đầu đọc trên xâu vào `aacbc` tại thời điểm này. Các luật sinh đã được áp dụng để tạo ra `aacb`.
Xâu vào là `aacbc`. Sau 4 bước, `aacb` đã được tạo ra. Khi áp dụng luật (1) S->aSbS ta được `aacbaSbS`. Như vậy khi so khớp đến đây, đầu đọc đã đọc đến ký tự thứ 5, tức là ký tự `c` trong xâu `aacbc`.
Do đó, đầu đọc đang trỏ tới ký tự 'c'.
