Cho hai DFA đầy đủ trên cùng bảng chữ cái. Hai DFA tương đương nếu chúng chấp nhận đúng cùng một ngôn ngữ. Duyệt đồng thời cặp trạng thái (x,y) bắt đầu từ (s1,s2); nếu tồn tại cặp đạt được mà một bên chấp nhận còn bên kia thì không, hai DFA khác nhau.
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:
2 2
1 0
0 1
0
1 1
3 2
1 0
2 1
1 2
0
2 1 2
Output:
NO
Hai khối DFA liên tiếp, mỗi khối theo định dạng: 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).
Hai DFA có cùng kích thước bảng chữ cái k.1 ≤ n1,n2 ≤ 1000, 1 ≤ k ≤ 26.
In YES nếu hai DFA tương đương, ngược lại NO.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
3 2
1 0
2 1
1 2
0
2 1 2
Đầu ra:
NO
Giải thích:
Đang tải editor...