Hai trạng thái p, q của một DFA là phân biệt được nếu tồn tại chuỗi z sao cho đúng một trong hai đường đi δ*(p,z), δ*(q,z) kết thúc ở trạng thái nhận.
Cho DFA trên {0,1} và hai trạng thái p, q, hãy in chuỗi z ngắn nhất, nhỏ nhất theo thứ tự từ điển phân biệt chúng (dùng BFS trên các cặp trạng thái). Nếu chúng đã khác nhau về tính nhận ngay tại chuỗi rỗng thì in dòng trống. Nếu không phân biệt được, in EQUIV.
Ví dụ: DFA đếm '1' mod 3, so p=1, q=2 → z = 1.
Dòng 1: n. n dòng: d0 d1. Dòng tiếp: các trạng thái nhận (có thể trống). Dòng tiếp: p q.
1 ≤ n ≤ 200, 0 ≤ p, q < n.
Một dòng: chuỗi phân biệt (có thể trống) hoặc EQUIV.
Ví dụ:
Đầu vào:
3
0 1
1 2
2 0
0
1 2
Đầu ra:
1
Giải thích:
Đang tải editor...