Cho văn phạm S → A hoặc S-> BCD; A → BBA hoặc A->EB; B → bEc hoặc B->BC hoặc B->BDc ; C → c ; D → a hoặc D-> BDb; E → a hoặc E->bE , First(A)=?

Trong lý thuyết ngôn ngữ hình thức, First(X) là tập hợp các ký tự đầu cuối có thể xuất hiện đầu tiên trong một chuỗi được dẫn xuất từ X.

Trong trường hợp này, C -> c, nên First(C) = {c}.

Để tìm First(D), ta cần xác định tập hợp các ký tự đầu cuối có thể xuất hiện đầu tiên khi suy dẫn từ D. Theo văn phạm đã cho, D → a hoặc D → BDb. Vì vậy:

• Từ D → a, ta có 'a' thuộc First(D).
• Từ D → BDb, ta cần tìm First(B). Theo văn phạm, B → bEc hoặc B → BC hoặc B → BDc. Do đó, 'b' thuộc First(B).
• Vì 'b' thuộc First(B) và D → BDb, nên 'b' cũng có thể xuất hiện ở đầu khi suy dẫn từ D.
• Tuy nhiên, cần lưu ý rằng C → c.
• Vậy, First(D) = {a, b}.

Để tìm Follow(A), ta cần xem xét các quy tắc sinh trong văn phạm mà A xuất hiện ở vế phải. Trong trường hợp này, A xuất hiện trong quy tắc S → A.

1. Vì A là ký tự đầu tiên trong quy tắc S → A và S là ký tự bắt đầu, $ (ký tự kết thúc) sẽ thuộc Follow(A).
2. Trong quy tắc A → BBA, B theo sau A. Do đó, First(B) cần được đưa vào Follow(A). First(B) = {b}. Vậy 'b' thuộc Follow(A). Tuy nhiên, vì có A -> EB, E có thể dẫn đến xâu rỗng, nên ta cần xem xét Follow(A) khi A đứng cuối. Trong quy tắc A -> BBA, A đứng cuối cùng, do đó Follow(S) cần được thêm vào Follow(A). Vì S là ký tự bắt đầu, Follow(S) = {$}
3. Trong quy tắc A -> EB, B theo sau E. Do đó, First(B) cần được đưa vào Follow(E). First(B) = {b}. Vậy 'b' thuộc Follow(E). Tuy nhiên, vì A -> EB, nên Follow(A) bao gồm Follow(B). First(B) = {b}. Vậy 'b' thuộc Follow(A).

Do đó, Follow(A) = {b, $}.

Vậy đáp án đúng là B. { b, dollar }