solution

Bước xác định hoá (subset construction, hay powerset construction) biến một $\varepsilon$-NFA thành DFA tương đương, trong đó mỗi trạng thái DFA tương ứng với một tập con trạng thái của NFA.

Cho một $\varepsilon$-NFA có $n$ trạng thái đánh số từ $0$ đến $n-1$ và $m$ cạnh chuyển (mỗi cạnh dạng $(u,v,c)$, với $c$ là một ký hiệu, hoặc chữ E cho chuyển epsilon), và trạng thái bắt đầu $s$. Thực hiện subset construction như sau: trạng thái DFA đầu tiên là $D_0 = \text{closure}(\{s\})$ (bao đóng epsilon của $\{s\}$). Với mỗi trạng thái DFA $D$ đã sinh ra và mỗi ký hiệu $c$ (không tính E) từng xuất hiện trong đồ thị NFA, tính

$D' = \text{closure}\Big(\bigcup_{u \in D} \{ v : (u,v,c) \text{ là một cạnh}\}\Big).$

Nếu $D'$ khác rỗng và chưa từng xuất hiện trước đó, $D'$ trở thành một trạng thái DFA mới. Quá trình lặp lại cho đến khi không còn trạng thái DFA mới nào được sinh ra.

Hãy đếm số trạng thái DFA có thể đến được (kể cả $D_0$), không tính trạng thái bẫy ứng với tập rỗng (khi $D' = \emptyset$ thì không có chuyển nào được tạo ra tại $D$ ứng với $c$ đó, và trạng thái này không được tính vào kết quả).

Ví dụ: NFA có $n=2$ trạng thái, một cạnh $(0,1,a)$, bắt đầu từ $s=0$. Ta có $D_0=\{0\}$; xét ký hiệu a: từ $D_0$ ta được $D_1=\{1\}$, thêm vào; từ $D_1$ không có chuyển a nào (vì $\{1\}$ không có cạnh đi ra) nên dừng. Tổng cộng có $2$ trạng thái DFA: $D_0$ và $D_1$.