Cho hai DFA đầy đủ trên cùng bảng chữ cái. Xây DFA tích với trạng thái là cặp (x,y); ngôn ngữ giao L1 ∩ L2 được chấp nhận tại cặp mà cả hai đều chấp nhận. Ngôn ngữ giao rỗng khi không có cặp chấp nhận nào đạt được từ (s1,s2).
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
2 2
0 1
1 0
0
1 1
Output:
NONEMPTY
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 NONEMPTY nếu L1 ∩ L2 ≠ ∅, ngược lại EMPTY.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
2 2
0 1
1 0
0
1 1
Đầu ra:
NONEMPTY
Giải thích:
Đang tải editor...