Cho một DFA đầy đủ. Ngôn ngữ của nó vô hạn khi và chỉ khi tồn tại một trạng thái hữu ích (vừa đạt được từ trạng thái đầu, vừa có thể dẫn tới một trạng thái chấp nhận) nằm trên một chu trình. Ngược lại ngôn ngữ hữu hạn. Hãy xác đị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:
3 2
1 0
2 0
2 2
0
1 2
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 ≤ 10^4, 1 ≤ k ≤ 26.
In INFINITE nếu ngôn ngữ vô hạn, ngược lại FINITE.
Ví dụ:
Đầu vào:
3 2
1 0
2 0
2 2
0
1 2
Đầu ra:
INFINITE
Giải thích:
Đang tải editor...