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. First(A)=?

Để tìm First(S), ta cần xem xét các luật sinh có S ở vế trái. Trong trường hợp này, ta có luật S -> AB.

1. Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật A -> 0A cho thấy A có thể dẫn xuất ra một chuỗi bắt đầu bằng '0'.
2. Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật A -> 1 cho thấy A có thể dẫn xuất ra '1'.
3. Nếu A dẫn xuất ra epsilon (chuỗi rỗng), ta cần xét đến B. Nếu B dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật B -> 0 cho thấy B có thể dẫn xuất ra '0'.
4. Nếu A dẫn xuất ra epsilon, và B dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật B -> 1A cho thấy B có thể dẫn xuất ra chuỗi bắt đầu bằng '1'.
5. Nếu A và B đều dẫn xuất ra epsilon, thì epsilon thuộc First(S).

Tuy nhiên, câu hỏi này chỉ yêu cầu First(S) mà không yêu cầu phải loại bỏ epsilon nếu có. Vậy, First(S) = {0, 1}.

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

• (1) S -> BA: FOLLOW(A) chứa FIRST(A) \ {ε}. Trong trường hợp này, FIRST(A) = {1, ε}, do đó FOLLOW(A) chứa {1}. Nếu ε thuộc FIRST(A) thì FOLLOW(A) chứa FOLLOW(S).
• (2) C -> A0: FOLLOW(A) chứa {0}.
• (4) B -> A1: FOLLOW(A) chứa {1}.

Kết hợp lại, FOLLOW(A) = {0, 1}.

Để tìm FOLLOW(S), ta cần xác định các ký tự có thể xuất hiện ngay sau S trong các chuỗi dẫn xuất từ văn phạm đã cho.

Tuy nhiên, S là ký hiệu bắt đầu, do đó theo định nghĩa, FOLLOW(S) luôn chứa ký hiệu kết thúc chuỗi (thường ký hiệu là $).

Vậy, FOLLOW(S) = {$} hay {dollar}.

Để tìm FIRST(S), ta cần xem xét các luật sinh bắt đầu từ S. Trong trường hợp này, S → A, vì vậy FIRST(S) = FIRST(A). Bây giờ ta xét A → BC hoặc A → DBC.

- Nếu A → BC, thì FIRST(A) = FIRST(BC). Vì B → bB’ hoặc B → ε, nên FIRST(B) = {b, ε}. Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Vì vậy, FIRST(BC) = {b} ∪ (nếu ε ∈ FIRST(B) thì FIRST(C) nếu không thì {ε}) = {b} ∪ {c, ε} = {b, c, ε}.

- Nếu A → DBC, thì FIRST(A) = FIRST(DBC). Vì D → a hoặc D → d, nên FIRST(D) = {a, d}. Vì vậy, FIRST(DBC) = {a, d}.

Vậy, FIRST(A) = FIRST(BC) ∪ FIRST(DBC) = {b, c, ε} ∪ {a, d} = {a, b, c, d, ε}.

Tuy nhiên, khi xem lại các đáp án thì không có đáp án nào chính xác hoàn toàn với phân tích trên. Đáp án gần đúng nhất là đáp án D, tuy nhiên nó thiếu 'd'.

Do không có đáp án chính xác, ta cần xem xét lại ngữ cảnh và có thể có một số giả định hoặc đơn giản hóa mà câu hỏi mong muốn.

Nếu câu hỏi chỉ xét đến việc tìm các terminal có thể xuất hiện đầu tiên từ S, bỏ qua trường hợp D -> d thì FIRST(S) = {a, b, c, epsilon}