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] Đếm số trạng thái của DFA tối tiểu

    Cho một DFA đầy đủ MMM. Hãy tối tiểu hóa (minimize) nó bằng cách loại các trạng thái không tới được và gộp các trạng thái tương đương (phân biệt được bằng Hopcroft/table-filling), rồi đếm số trạng thái của DFA tối tiểu tương đương.

    Hai trạng thái p,qp,qp,q tương đương nếu ∀w: δ^(p,w)∈F  ⟺  δ^(q,w)∈F\forall w:\ \hat\delta(p,w)\in F \iff \hat\delta(q,w)\in F∀w: δ^(p,w)∈F⟺δ^(q,w)∈F. DFA tối tiểu là duy nhất (sai khác đổi tên).

    Lưu ý: chỉ tính các trạng thái tới được từ trạng thái bắt đầu trước khi gộp.

    Ví dụ: một DFA 444 trạng thái có thể tối tiểu còn 222.

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

      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).

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

      1≤Q≤5001 \le Q \le 5001≤Q≤500, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26. DFA đầy đủ.

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

      In một số nguyên: số trạng thái của DFA tối tiểu.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    3

    Giải thích:

    Trạng thái 0 và 2 tương đương (cùng hành vi), gộp lại. DFA tối tiểu còn 3 trạng thái.

    Đang tải editor...