FOLLOW(S), với S là ký hiệu bắt đầu của một văn phạm bất kỳ thì FOLLOW(S) luôn luôn bao gồm ký hiệu nào?

Để tìm Follow(A), ta thực hiện theo các bước sau:

• Nếu A là kí hiệu bắt đầu, thì $ ∈ Follow(A). Trong trường hợp này, A không phải là kí hiệu bắt đầu.
• Nếu có luật sinh B -> αAβ, thì mọi phần tử của First(β) (ngoại trừ ε) nằm trong Follow(A). Ở đây ta có luật S -> AB, nên First(B) nằm trong Follow(A). First(B) = {b}, do đó b ∈ Follow(A).
• Nếu có luật sinh B -> αA hoặc B -> αAβ, trong đó First(β) chứa ε, thì mọi phần tử của Follow(B) nằm trong Follow(A). Ở đây ta có S -> AB và B -> ε, nên Follow(S) nằm trong Follow(A). Vì S là ký hiệu bắt đầu, Follow(S) = {$} do đó $ ∈ Follow(A).

Vậy Follow(A) = {b, $}.

Để tìm FOLLOW(S), ta xét các luật sinh có S ở vế trái hoặc vế phải.

- Ta có luật sinh S → A, nên FOLLOW(S) sẽ chứa tất cả các phần tử của FOLLOW(A).

- Bây giờ ta cần tìm FOLLOW(A). Xét các luật sinh có A ở vế phải: S → A; A → BC; A → DBC.

+ Từ S → A, ta suy ra FOLLOW(A) chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, nên $ thuộc FOLLOW(S).

+ Từ A → BC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).

+ Từ A → DBC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).

+ Từ A → BC, ta suy ra nếu C → ε thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(C) (nếu C dẫn xuất ra ε). FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(A) chứa FOLLOW(S)={$} .

+ Từ A → DBC, ta suy ra FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(S)={$} .

Vậy FOLLOW(A) chứa {$}. Do đó, FOLLOW(S) chứa {$}.

Đáp án đúng là D.

Để tìm First(S), ta cần xem xét các sản xuất của S:

S → A

S → BCD

Với S → A, ta cần tìm First(A). Các sản xuất của A là:

A → BBA

A → EB

Với A → BBA, ta cần tìm First(B). Các sản xuất của B là:

B → bEc

B → BC

B → BDc

First(B) = {b}.

Với A → EB, ta cần tìm First(E). Các sản xuất của E là:

E → a

E → bE

First(E) = {a, b}.

Vậy First(A) = First(B) ∪ First(E) = {b} ∪ {a, b} = {a, b}.

Do đó, nếu S → A thì First(S) chứa {a, b}.

Với S → BCD, ta cần tìm First(B). Như đã thấy, First(B) = {b}.

Vậy First(S) chứa {b}.

Tuy nhiên, chúng ta cần xem xét kỹ hơn sản xuất B → BC. Điều này có nghĩa là B có thể dẫn đến chuỗi rỗng (nếu C dẫn đến rỗng), do đó ta cần xem xét First(C) nếu B có thể dẫn đến rỗng.

First(C) = {c}.

Vậy nếu S → BCD, First(S) có thể chứa {b, c}.

Kết hợp lại, First(S) = First(A) ∪ First(BCD) = {a, b} ∪ {b, c} = {a, b, c}.