Cho văn phạm G = {S ->aAAB; S->bC; A-> bB; A-> epsilon; B-> Aa; B->A; B- >epsilon; C ->bA; C->B} Sau khi loại bỏ các sản xuất rỗng trong G, có bao nhiêu luật sinh có vế trái là S
Trả lời:
Đáp án đúng: A
Để loại bỏ các sản xuất rỗng trong văn phạm G, ta thực hiện các bước sau:
1. **Tìm các biến có thể dẫn đến rỗng (epsilon):**
- Từ A -> epsilon, B -> epsilon, ta có A và B có thể dẫn đến rỗng.
2. **Loại bỏ các sản xuất rỗng:**
- Thay thế các luật sinh có A hoặc B ở vế phải bằng các luật sinh mới, trong đó A hoặc B có thể có hoặc không.
Áp dụng vào văn phạm G:
G = {S -> aAAB; S -> bC; A -> bB; A -> epsilon; B -> Aa; B -> A; B -> epsilon; C -> bA; C -> B}
- S -> aAAB:
A và B có thể rỗng, nên ta có các luật sinh mới:
- S -> aAAB
- S -> aAA
- S -> aAB
- S -> aA
- S -> aB
- S -> a
- S -> aBB
- S -> aB (trùng với S -> aB, bỏ qua)
- S -> bC: Giữ nguyên (S -> bC)
Vậy các luật sinh có vế trái là S sau khi loại bỏ sản xuất rỗng là:
S -> aAAB
S -> aAA
S -> aAB
S -> aA
S -> aB
S -> a
S -> aBB
S -> bC
Có tổng cộng 8 luật sinh có vế trái là S.
