Cho một NFA (không ε). Áp dụng subset construction để chuyển thành DFA: mỗi trạng thái DFA là một tập con các trạng thái NFA đạt được từ tập bắt đầu {s}. Hãy đếm số trạng thái DFA đạt được khác rỗng (bỏ qua trạng thái bẫy ứng với tập rỗng).
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
3 2
4
0 0 0
0 1 0
0 0 1
1 1 2
0
1 2
Output:
3
Khối mô tả NFA gồm:
n k.t — số bộ chuyển.t dòng: mỗi dòng u j v nghĩa là từ trạng thái u đọc ký tự thứ j có thể tới v (không đơn định).s.f rồi f số — tập chấp nhận.1 ≤ n ≤ 18, 1 ≤ k ≤ 26.
In một số nguyên: số trạng thái khác rỗng của DFA sinh ra.
Ví dụ:
Đầu vào:
3 2
4
0 0 0
0 1 0
0 0 1
1 1 2
0
1 2
Đầu ra:
3
Giải thích:
Đang tải editor...