solution

Cho một văn phạm phi ngữ cảnh nhỏ, ký hiệu bắt đầu là vế trái của sản xuất đầu tiên trong danh sách. Quy ước ký hiệu (giống bài phát hiện xung đột SLR(1)): ký hiệu bắt đầu bằng chữ in hoa là non-terminal, mọi ký hiệu khác là terminal.

Hãy xây dựng tự động LR(0) chuẩn tắc (canonical LR(0) automaton) của văn phạm theo đúng thuật toán kinh điển:

1. Thêm sản xuất mở rộng $S' \to S$, trong đó $S$ là ký hiệu bắt đầu (đảm bảo $S'$ không trùng với bất kỳ ký hiệu nào đã xuất hiện trong văn phạm gốc).
2. Trạng thái ban đầu $I_0 = \text{closure}(\{S' \to \cdot S\})$, với $\text{closure}$ được tính bằng cách: với mọi mục $A \to \alpha \cdot B \beta$ trong tập ($B$ là non-terminal), thêm vào tập tất cả các mục $B \to \cdot \gamma$ ứng với mọi sản xuất $B \to \gamma$, lặp lại tới khi tập không đổi.
3. Với mỗi trạng thái $I$ đã có và mỗi ký hiệu văn phạm $X$ (terminal hoặc non-terminal) mà có mục dạng $A \to \alpha \cdot X \beta$ trong $I$: $\text{goto}(I, X) = \text{closure}(\{A \to \alpha X \cdot \beta \mid A \to \alpha \cdot X \beta \in I\})$. Nếu tập kết quả khác rỗng và chưa tồn tại như một trạng thái, thêm nó vào tập hợp các trạng thái.
4. Lặp lại bước 3 cho tới khi không còn trạng thái mới nào được sinh ra.

Yêu cầu: cho biết tổng số trạng thái (số tập mục — item set) phân biệt trong tự động LR(0) chuẩn tắc thu được (bao gồm cả $I_0$).

Ví dụ: với văn phạm chỉ có 1 sản xuất S -> a, tự động LR(0) có đúng 3 trạng thái: $I_0 = \{S' \to \cdot S,\ S \to \cdot a\}$, $I_1 = \{S' \to S \cdot\}$ (từ $\text{goto}(I_0, S)$), $I_2 = \{S \to a \cdot\}$ (từ $\text{goto}(I_0, a)$). Kết quả in ra: 3.