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 qua xây tập con

    Chuyển biểu thức chính quy R sang DFA bằng xây tập con (subset construction) trên bảng chữ Σ: trạng thái DFA là các tập trạng thái NFA (đã lấy bao đóng epsilon) tới được từ trạng thái đầu; kể cả trạng thái chết (tập rỗng) nếu tới được. Đếm số trạng thái DFA.

    Lưu ý: đây không phải DFA tối thiểu.

    Ví dụ: Σ={a,b}, R=(a|b)*abb → 5 trạng thái.

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

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

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

      |Σ| ≤ 10, |R| ≤ 200.

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

      In số trạng thái DFA (xây tập con, tới được).

    Ví dụ:

    Đầu vào:

    ab
(a|b)*abb

    Đầu ra:

    5

    Giải thích:

    Xây tập con cho 5 trạng thái tới được.

    Đang tải editor...