Cho văn phạm với các luật sinh: S->AS, S->b, A->SA, A->a Kí hiệu I0 là tập mục đầu tiên của văn phạm, phép toán Goto(I0,A) =?

Để tìm FIRST(A), ta cần xác định tập hợp các terminal có thể xuất hiện đầu tiên khi suy dẫn từ A.

• A -> hSg
• S -> aAb | c

Từ luật sinh A -> hSg, ta thấy rằng mọi chuỗi suy dẫn từ A sẽ bắt đầu bằng 'h'. Do đó, 'h' thuộc FIRST(A).

Vậy, FIRST(A) = {h}.

Để tìm First(A), ta xét các luật sinh có A ở vế trái:

• A -> 0A: Vì bắt đầu bằng terminal 0, nên 0 thuộc First(A)
• A -> 1: Vì bắt đầu bằng terminal 1, nên 1 thuộc First(A)
• A -> epsilon: Vì A có thể dẫn đến epsilon, nên epsilon thuộc First(A)

Vậy First(A) = {0, 1, epsilon}

Để tìm FOLLOW(B), ta cần xem xét các luật sinh có B ở vế phải. FOLLOW(B) là tập hợp các terminal có thể xuất hiện ngay sau B trong quá trình dẫn xuất.

1. Từ luật S -> BA, FOLLOW(B) chứa FIRST(A). FIRST(A) = {1, epsilon}. Tuy nhiên, nếu FIRST(A) chứa epsilon, thì FOLLOW(B) cũng chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, nên $ thuộc FOLLOW(S).

2. Xem xét luật khác không có B ở vế phải.

3. Vì A -> epsilon, nên từ S -> BA, ta có FOLLOW(B) chứa FOLLOW(S). Giả sử S không xuất hiện ở vế phải của bất kỳ luật nào, ta không cần phải xem xét thêm.

4. Do A->1 và A->epsilon, nên FIRST(A) = {1}. Vì A có thể dẫn xuất ra epsilon, FOLLOW(B) sẽ chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, FOLLOW(S) chứa $.

5. Vì B có thể là cuối chuỗi (S -> BA, A -> epsilon), nên FOLLOW(B) có thể chứa $ (end marker).

Tuy nhiên, vì không có dấu $ trong các lựa chọn, ta cần xem xét kỹ hơn. Từ S -> BA, nếu A -> 1 thì B đứng trước 1, nếu A -> epsilon thì B đứng cuối chuỗi, nhưng không có terminal nào theo sau. Nhưng nếu A -> epsilon, ta có thể coi như B là cuối của S.

Từ S -> BA, FIRST(A) = {1, epsilon}. Nếu epsilon thuộc FIRST(A), thì FOLLOW(B) sẽ chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, FOLLOW(S) chứa $, nhưng $ không có trong các đáp án. Trong trường hợp này, khi A -> 1, thì 1 thuộc FIRST(A). Khi A -> epsilon, thì không có gì theo sau B.

Tuy nhiên, ta cần xem xét kỹ các luật sinh. S -> BA, A -> 1 hoặc A -> epsilon. Vậy FOLLOW(B) chứa FIRST(A) ngoại trừ epsilon. Do đó, FOLLOW(B) chứa {1}. Nếu A -> epsilon, thì FOLLOW(B) chứa FOLLOW(S), tức là không có gì cả. Vì không có đáp án nào là {1}, ta cần xem xét lại.

Nếu ta có thêm một luật sinh nữa có dạng X -> BY, thì FOLLOW(B) sẽ chứa FIRST(Y). Nhưng ở đây không có.

Nếu A -> 0, thì ta sẽ có 0 thuộc FIRST(A), vậy 0 thuộc FOLLOW(B). Nhưng A -> 1 hoặc epsilon, không phải A -> 0.

Như vậy, chúng ta có A -> 1 hoặc A -> epsilon. Nên FOLLOW(B) chỉ chứa 1 khi A -> 1.

Xét luật B -> A1. Ta thấy 1 luôn theo sau A. Vậy A thuộc FIRST(B). Khi đó, A -> 1 và A -> epsilon, suy ra 1 thuộc FIRST(A). Do đó, FIRST(A) = {1}.

Vậy FOLLOW(B) chứa FIRST(A) = {1}.

Đáp án chính xác nhất là B. {1}