Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Kiểm tra hai DFA có tương đương không

    Cho hai DFA đầy đủ M1,M2M_1,M_2M1​,M2​ trên cùng bảng chữ cái. Xác định chúng có tương đương không, tức L(M1)=L(M2)L(M_1)=L(M_2)L(M1​)=L(M2​).

    Thuật toán tích (product/cross): duyệt BFS trên các cặp trạng thái (p,q)(p,q)(p,q) bắt đầu từ (q01,q02)(q_0^1,q_0^2)(q01​,q02​); nếu gặp cặp mà đúng một trạng thái là chấp nhận thì hai DFA khác nhau.

    Ví dụ: hai DFA cùng nhận "số 111 chẵn" nhưng vẽ khác nhau vẫn tương đương.

    • Định dạng đầu vào:

      Đầu vào gồm hai DFA liên tiếp, mỗi DFA theo định dạng: Dòng 1: số trạng thái QQQ (đánh số 0..Q−10..Q-10..Q−1). Dòng 2: bảng chữ cái Σ\SigmaΣ (cách nhau dấu cách). Dòng 3: trạng thái bắt đầu. Dòng 4: số trạng thái chấp nhận rồi danh sách trạng thái chấp nhận (cùng dòng). Tiếp theo Q×∣Σ∣Q\times|\Sigma|Q×∣Σ∣ dòng p a q nghĩa là δ(p,a)=q\delta(p,a)=qδ(p,a)=q (DFA đầy đủ — mọi cặp (p,a)(p,a)(p,a) có đúng một đích). Hai DFA dùng chung bảng chữ cái (ghi lại trong từng khối).

    • Ràng buộc đầu vào:

      1≤Qi≤3001 \le Q_i \le 3001≤Qi​≤300, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26. Hai DFA đầy đủ, cùng Σ\SigmaΣ.

    • Định dạng đầu ra:

      In EQUIVALENT nếu L(M1)=L(M2)L(M_1)=L(M_2)L(M1​)=L(M2​), ngược lại DIFFERENT.

    Ví dụ:

    Đầu vào:

    2
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
3
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
2 0 2
2 1 2

    Đầu ra:

    EQUIVALENT

    Giải thích:

    Cả hai nhận 'số 1 chẵn'; DFA thứ hai có thêm trạng thái 2 không tới được. Tích chỉ thăm cặp reachable, không thấy mâu thuẫn -> EQUIVALENT.

    Đang tải editor...