solution

Cho văn phạm phi ngữ cảnh $G$ với ký hiệu bắt đầu $S$. Văn phạm mở rộng (augmented grammar) $G'$ được tạo bằng cách thêm luật sinh mới $S' \to S$ với $S'$ là ký hiệu bắt đầu mới (không trùng với bất kỳ ký hiệu nào đã có trong $G$).

Quy ước ký hiệu văn phạm (áp dụng cho toàn bộ đề bài này): mỗi luật sinh được cho ở dạng A -> X1 X2 ... Xk (các ký hiệu cách nhau bởi dấu cách); nếu vế phải là rỗng thì ghi A -> eps. Một ký hiệu được coi là ký hiệu chưa kết thúc (non-terminal) nếu và chỉ nếu ký tự đầu tiên của nó là một chữ cái in hoa (A-Z); mọi ký hiệu còn lại (chữ thường, chữ số, dấu (, ), +, id, ... ) đều là ký hiệu kết thúc (terminal). Ký hiệu đặc biệt eps chỉ dùng để biểu diễn xâu rỗng $\varepsilon$ và không phải là một terminal thật sự. Ký hiệu $ là ký hiệu kết thúc xâu vào (end-marker).

Mục LR(0) có dạng $[A \to \alpha \cdot \beta]$ (một luật sinh với một dấu chấm . đặt ở một vị trí nào đó trong vế phải). Phép closure$(I)$: với mỗi mục $[A \to \alpha \cdot B \beta] \in I$ mà $B$ là non-terminal, thêm mọi mục $[B \to \cdot \gamma]$ (với $B \to \gamma$ là luật sinh của $B$) vào $I$, lặp lại đến khi không còn gì thay đổi. Phép goto$(I, X)$ (với $X$ là một ký hiệu bất kỳ): tập hợp mọi mục $[A \to \alpha X \cdot \beta]$ sao cho $[A \to \alpha \cdot X \beta] \in I$, sau đó lấy closure của tập đó.

Họ tập mục chính tắc (canonical collection): bắt đầu từ $I_0 = \mathrm{closure}(\{[S' \to \cdot S]\})$, lặp đi lặp lại việc tính $\mathrm{goto}(I, X)$ cho mọi trạng thái $I$ đã có và mọi ký hiệu $X$ của văn phạm, thêm các trạng thái mới (tập mục khác với mọi tập mục đã có) cho tới khi không phát sinh thêm trạng thái nào — đây chính là các trạng thái của ôtômat LR(0), nền tảng để xây bảng SLR(1)/LALR(1).

Hãy xác định: (1) tổng số trạng thái (tập mục) phân biệt trong họ tập mục chính tắc, và (2) tổng số cạnh chuyển phân biệt của ôtômat, trong đó một cạnh được tính là một cặp (trạng thái nguồn, ký hiệu chuyển) $(I, X)$ mà $\mathrm{goto}(I,X)$ khác rỗng (nếu từ cùng một trạng thái $I$ có cạnh nhãn $X$ đi tới đúng một trạng thái đích duy nhất theo định nghĩa goto, mỗi cặp $(I,X)$ hợp lệ chỉ tính 1 cạnh, kể cả khi đích trùng với một trạng thái đã tồn tại hoặc trùng với chính $I$ — tự vòng lặp cũng tính là 1 cạnh).

Ví dụ: văn phạm S -> a với ký hiệu bắt đầu S có $I_0 = \{[S' \to \cdot S],[S \to \cdot a]\}$, $\mathrm{goto}(I_0,S)=\{[S' \to S \cdot]\}$, $\mathrm{goto}(I_0,a)=\{[S \to a \cdot]\}$ — có 3 trạng thái, 2 cạnh.