Cho NFA không epsilon N=(Q,Σ,δ,q0,F). Áp dụng xây dựng tập con (subset construction) để chuyển NFA thành DFA tương đương. Hãy đếm số trạng thái tới được (reachable) của DFA kết quả.
Mỗi trạng thái DFA là một tập con của Q. Bắt đầu từ {q0}; với mỗi ký tự a, chuyển tới ⋃s∈Sδ(s,a) (bao gồm cả tập rỗng nếu có). Đếm số tập con khác nhau sinh ra.
Lưu ý: tập rỗng (trạng thái bẫy) nếu xuất hiện cũng được tính là một trạng thái.
Ví dụ: NFA nhận chuỗi kết thúc 1 có DFA tương đương 2 trạng thái.
Dòng 1: số trạng thái Q (đánh số 0..Q−1).
Dòng 2: bảng chữ cái Σ (cách nhau dấu cách).
Dòng 3: trạng thái bắt đầu q0.
Dòng 4: số trạng thái chấp nhận rồi danh sách trạng thái chấp nhận.
Dòng 5: số bước chuyển T.
Tiếp theo T dòng, mỗi dòng p a q nghĩa là q∈δ(p,a) (NFA, có thể nhiều đích cho cùng (p,a)).
1≤Q≤16, 1≤∣Σ∣≤5. (Số tập con có thể lớn nên hạn chế Q.)
In một số nguyên: số trạng thái tới được của DFA sau xây dựng tập con.
Ví dụ:
Đầu vào:
2
0 1
0
1 1
3
0 0 0
0 1 0
0 1 1
Đầu ra:
2
Giải thích:
Đang tải editor...