solution

Bộ dựng Thompson (Thompson construction) biến một biểu thức chính quy thành một NFA có $\varepsilon$-dịch chuyển. Trong bài này, quy tắc dựng được cố định như sau (số trạng thái và số dịch chuyển của mỗi mảnh NFA con):

• Kí tự đơn $c$: mảnh gồm $2$ trạng thái, $1$ dịch chuyển.
• Nối tiếp $e_1 \cdot e_2$ (kí hiệu .): gộp trạng thái kết thúc của $e_1$ với trạng thái bắt đầu của $e_2$ thành một. Số trạng thái $=s_1+s_2-1$; số dịch chuyển $=t_1+t_2$.
• Hội $e_1\mid e_2$ (kí hiệu |): thêm $1$ trạng thái bắt đầu mới, $1$ trạng thái kết thúc mới, và $4$ dịch chuyển $\varepsilon$ nối chúng với $e_1,e_2$. Số trạng thái $=s_1+s_2+2$; số dịch chuyển $=t_1+t_2+4$.
• Lặp Kleene $e^{*}$ (kí hiệu *): thêm $1$ trạng thái bắt đầu mới, $1$ trạng thái kết thúc mới, và $4$ dịch chuyển $\varepsilon$. Số trạng thái $=s+2$; số dịch chuyển $=t+4$.

Cho biểu thức chính quy viết dưới dạng hậu tố (postfix, không dấu ngoặc) chỉ gồm chữ cái thường a-z (toán hạng) và ba toán tử ., |, *, hãy tính tổng số trạng thái và tổng số dịch chuyển (kể cả $\varepsilon$) của NFA thu được khi dựng theo Thompson với quy tắc trên.