Cho một DFA đầy đủ. Nếu ngôn ngữ vô hạn, in INFINITE. Nếu hữu hạn, in tổng số chuỗi được chấp nhận (số này có thể lớn nhưng hữu hạn — in giá trị chính xác). Xét các trạng thái hữu ích (đạt được và có thể dẫn tới chấp nhận); nếu chúng tạo chu trình thì vô hạn, ngược lại đếm số đường đi (số chuỗi) trên đồ thị không chu trình.
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:
4 2
1 2
3 3
3 3
3 3
0
1 3
Output:
INFINITE
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).1 ≤ n ≤ 2000, 1 ≤ k ≤ 26.
In INFINITE nếu ngôn ngữ vô hạn; ngược lại in tổng số chuỗi được chấp nhận.
Ví dụ:
Đầu vào:
4 2
1 2
3 3
3 3
3 3
0
1 3
Đầu ra:
INFINITE
Giải thích:
Đang tải editor...