Cho hai NFA (không ε) trên cùng bảng chữ cái. Hãy chuyển mỗi NFA thành DFA đầy đủ bằng subset construction, rồi kiểm tra hai DFA có tương đương không (duyệt cặp trạng thái trên DFA tích). In kết quả tương đương của hai NFA.
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
3
0 0 1
1 0 1
1 1 1
0
1 1
2 2
4
0 0 0
0 0 1
1 0 1
1 1 1
0
1 1
Output:
YES
Hai khối NFA liên tiếp, mỗi khối theo định dạng: 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.
Hai NFA có cùng kích thước bảng chữ cái k.1 ≤ n1,n2 ≤ 12, 1 ≤ k ≤ 26.
In YES nếu hai NFA nhận cùng ngôn ngữ, ngược lại NO.
Ví dụ:
Đầu vào:
2 2
3
0 0 1
1 0 1
1 1 1
0
1 1
2 2
4
0 0 0
0 0 1
1 0 1
1 1 1
0
1 1
Đầu ra:
YES
Giải thích:
Đang tải editor...