Cho hai DFA đầy đủ A và B trên cùng bảng chữ cái. Hãy kiểm tra L(A) ⊆ L(B) (mọi chuỗi được A chấp nhận cũng được B chấp nhận). Tương đương với L(A) ∩ complement(L(B)) = ∅: trên DFA tích, không tồn tại cặp đạt được mà A chấp nhận nhưng B từ chối.
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
1 2
0 0
0
1 0
Output:
YES
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 L(A) ⊆ L(B), ngược lại NO.
Ví dụ:
Đầu vào:
3 2
1 0
2 0
2 2
0
1 2
1 2
0 0
0
1 0
Đầu ra:
YES
Giải thích:
Đang tải editor...