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 trạng thái DFA tối thiểu

    Chuyển biểu thức chính quy R sang DFA rồi tối thiểu hóa (gộp các trạng thái tương đương bằng làm mịn phân hoạch – Moore/Hopcroft). In số trạng thái của DFA tối thiểu (tính cả trạng thái chết nếu cần để DFA đầy đủ trên Σ).

    Ví dụ: Σ={a,b}, R=(a|b)*abb → 4.

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

      Dòng 1: Σ. Dòng 2: R.

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

      |Σ| ≤ 6, |R| ≤ 200.

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

      In số trạng thái DFA tối thiểu.

    Ví dụ:

    Đầu vào:

    ab
(a|b)*abb

    Đầu ra:

    4

    Giải thích:

    DFA tối thiểu của `(a|b)*abb` có 4 trạng thái.

    Đang tải editor...