Lớp chính quy đóng dưới phần bù: nếu L chính quy thì Σ* \ L cũng chính quy (đảo trạng thái nhận/không nhận của DFA).
Cho một DFA trên bảng chữ {0,1} và chuỗi w, hãy cho biết w có thuộc phần bù của ngôn ngữ DFA hay không (tức DFA không chấp nhận w).
DFA cho ở đây nhận diện "số chữ số 1 là chẵn"; phần bù là "số chữ số 1 lẻ".
Dòng 1: n (số trạng thái 0..n-1). n dòng tiếp: mỗi dòng d0 d1 (trạng thái đích khi đọc '0' và '1'). Dòng tiếp: trạng thái đầu. Dòng tiếp: các trạng thái nhận (cách nhau dấu cách, có thể trống). Dòng cuối: chuỗi w.
1 ≤ n ≤ 50, |w| ≤ 200, w ∈ {0,1}*.
Một dòng: YES nếu w thuộc phần bù, ngược lại NO.
Ví dụ:
Đầu vào:
2
0 1
1 0
0
0
1
Đầu ra:
YES
Giải thích:
Đang tải editor...