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(S)=?
Đáp án đúng: A
Để 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}.
