Lớp chính quy đóng dưới phép hợp: L₁ ∪ L₂ chính quy (dựng DFA tích chạy song song hai DFA).
Cho hai DFA trên {0,1} và chuỗi w, hãy cho biết w ∈ L₁ ∪ L₂ — tức ít nhất một trong hai DFA chấp nhận w.
Ở đây L₁ = "số chữ số 1 chẵn", L₂ = "có ít nhất một chữ số 0".
Khối DFA gồm: dòng n, n dòng d0 d1, dòng trạng thái đầu, dòng các trạng thái nhận. Hai khối DFA liên tiếp, sau đó là dòng chuỗi w.
1 ≤ n ≤ 50 mỗi DFA, |w| ≤ 200, w ∈ {0,1}*.
Một dòng: YES nếu w ∈ L₁ ∪ L₂, ngược lại NO.
Ví dụ:
Đầu vào:
2
0 1
1 0
0
0
2
1 0
1 1
0
1
11
Đầu ra:
YES
Giải thích:
Đang tải editor...