Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B->1A; (5) B- >0. Phân tích xâu vào “0111” bằng thuật toán Topdown. Chọn lần lượt các sản xuất (1) (2) (2) (3) (5) (4) (3) để phân tích thì tại thời điểm này cây suy dẫn có bao nhiêu nút?

Để phân tích xâu "1011" bằng thuật toán Topdown với văn phạm đã cho và chuỗi sản xuất (1) (2) (2) (3) (5) (4) (3), ta cần xem xét quá trình phân tích và số lần quay lui:

1. (1) S -> AB: Bắt đầu với luật sinh đầu tiên.
2. (2) A -> 0A: Thay A bằng 0A. Lúc này ta có 0AB.
3. (2) A -> 0A: Thay A bằng 0A. Lúc này ta có 00AB.
4. (3) A -> 1: Thay A bằng 1. Lúc này ta có 001B.
5. (5) B -> 0: Thay B bằng 0. Lúc này ta có 0010. Chuỗi này không khớp với "1011", cần quay lui.
6. Quay lui 1: Quay lại bước 4, loại bỏ A -> 1.
7. (4) B -> 1A: Thay B bằng 1A. Lúc này ta có 00A1A, không khớp, cần quay lui.
8. Quay lui 2: Quay lại bước 3, loại bỏ A -> 0A.
9. (3) A -> 1: Thay A bằng 1 (ở luật sinh thứ (2)). Lúc này ta có 01B.
10. (5) B -> 0: Thay B bằng 0. Lúc này ta có 010. Chuỗi này không khớp với "1011", cần quay lui.
11. Quay lui 3: Quay lại bước 9, loại bỏ B -> 0.
12. (4) B -> 1A: Thay B bằng 1A. Lúc này ta có 011A.
13. (3) A -> 1: Thay A bằng 1. Lúc này ta có 0111, không khớp, cần quay lui.
14. Quay lui 4: Quay lại bước 2, loại bỏ A -> 0A.
15. (3) A -> 1: Thay A bằng 1. Lúc này ta có 1B.
16. (5) B -> 0: Thay B bằng 0. Lúc này ta có 10, không khớp, cần quay lui.
17. Quay lui 5: Quay lại bước 15, loại bỏ B -> 0.
18. (4) B -> 1A: Thay B bằng 1A. Lúc này ta có 11A.
19. (3) A -> 1: Thay A bằng 1. Lúc này ta có 111, không khớp, cần quay lui.
Quá trình trên cho thấy cần quay lui nhiều lần để đạt được xâu "1011". Tuy nhiên, với chuỗi sản xuất (1) (2) (2) (3) (5) (4) (3), số lần quay lui để *thử* phân tích rồi thất bại là đáng kể, nhưng câu hỏi chỉ hỏi số lần quay lui *để đạt trạng thái thành công*. Vì không có trạng thái thành công với chuỗi sản xuất này, nên cần xem lại cách tiếp cận. Theo đề bài, chọn lần lượt các sản xuất (1) (2) (2) (3) (5) (4) (3), ta thấy cần ít nhất 2 lần quay lui để có thể đến gần trạng thái đúng.
Do đó, đáp án đúng là 2.

Phân tích xâu "1011" theo thuật toán Bottom-up (từ dưới lên) nghĩa là bắt đầu từ xâu đã cho và tìm cách rút gọn nó về ký hiệu bắt đầu S theo các luật sinh ngược. Không có đáp án nào đúng vì không có quá trình phân tích nào có thể rút gọn "1011" về S sử dụng các luật sinh đã cho.

Phân tích xâu "1011" bằng thuật toán Bottom-up:
1. Gạt: Đọc ký tự đầu tiên '1' vào ngăn xếp. Ngăn xếp: $1, Xâu vào: 011$
2. Thu gọn theo (4): Thay '1' bằng 'A' theo luật A -> 1. Ngăn xếp: $A, Xâu vào: 011$
3. Gạt: Đọc ký tự tiếp theo '0' vào ngăn xếp. Ngăn xếp: $A0, Xâu vào: 11$
4. Thu gọn theo (2) KHÔNG THỂ, phải là (3): A->A0 (sai), A -> B0 (đúng). Ngăn xếp: $B, Xâu vào: 11$

Như vậy trạng thái phân tích sau các bước trên là: Ngăn xếp $A; Xâu vào: 011$.

Để tìm First(A), ta cần xem xét các luật sinh có A ở vế trái và tìm các terminal có thể bắt đầu từ A.

\n

- Luật (2): A -> 0A, cho thấy 0 có thể là ký tự đầu tiên của A. Vì vậy, 0 ∈ First(A).

\n

- Luật (3): A -> 1, cho thấy 1 có thể là ký tự đầu tiên của A. Vì vậy, 1 ∈ First(A).

\n

Do đó, First(A) = {0, 1}.