solution

Thuật toán Thompson construction xây dựng NFA từ biểu thức chính quy bằng cách ghép các "mảnh" NFA (fragment) đệ quy theo cấu trúc cú pháp của biểu thức. Hãy tính tổng số trạng thái của NFA thu được — chỉ dựa trên quy tắc đếm, không cần dựng tường minh đồ thị NFA.

Bảng chữ cái gồm các ký hiệu là chữ cái thường (a-z) hoặc chữ số (0-9). Biểu thức chính quy $R$ được xây dựng từ các ký hiệu đó bằng: phép nối liền kề (concatenation, viết các biểu thức con liền nhau), phép hợp | (độ ưu tiên thấp nhất, kết hợp trái), và các toán tử hậu tố *, +, ? (độ ưu tiên cao nhất, áp dụng cho biểu thức con ngay trước nó, có thể áp dụng liên tiếp nhiều lần); dấu ngoặc đơn ( ) dùng để nhóm. $R$ luôn hợp lệ về cú pháp (ngoặc cân xứng, không có toán hạng rỗng, không có khoảng trắng).

Quy tắc đếm số trạng thái theo Thompson construction chuẩn (như trình bày trong các giáo trình trình biên dịch):

• Một ký hiệu đơn tạo ra một mảnh NFA gồm đúng $2$ trạng thái (trạng thái bắt đầu và trạng thái kết thúc của mảnh, nối với nhau bằng một cạnh đọc ký hiệu đó): $\text{size} = 2$.
• Phép nối $R_1 R_2$: hợp nhất trạng thái kết thúc của mảnh $R_1$ với trạng thái bắt đầu của mảnh $R_2$ thành một trạng thái duy nhất (không tạo trạng thái mới nào khác): $\text{size}(R_1 R_2) = \text{size}(R_1) + \text{size}(R_2) - 1$.
• Phép hợp $R_1 \mid R_2$: tạo thêm đúng $2$ trạng thái mới (một trạng thái bắt đầu mới rẽ hai nhánh epsilon tới hai mảnh con, một trạng thái kết thúc mới nhận epsilon từ hai mảnh con): $\text{size}(R_1 \mid R_2) = \text{size}(R_1) + \text{size}(R_2) + 2$.
• Mỗi toán tử hậu tố $R^*$, $R^+$, $R^?$ đều tạo thêm đúng $2$ trạng thái mới so với mảnh con bên trong: $\text{size} = \text{size}(R) + 2$ (dù ba toán tử này có cấu trúc cạnh nối khác nhau, số trạng thái tăng thêm là như nhau).

Ví dụ (biểu thức kinh điển trong giáo trình): với $R =$ (a|b)*abb, NFA theo Thompson construction có đúng $11$ trạng thái.