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 NFA theo Thompson

    Dựng NFA cho biểu thức chính quy theo quy tắc Thompson sau, rồi đếm tổng số trạng thái:

    • Mỗi atom (một ký tự thường, ., hoặc @ = tập rỗng) tạo 2 trạng thái.
    • Mỗi toán tử hậu tố *, +, ? thêm 2 trạng thái.
    • Mỗi cụm hợp | (gộp các nhánh tại một cấp) thêm 2 trạng thái.
    • Phép nối không thêm trạng thái.
    • Một nhánh rỗng (ví dụ trong a|) tính như một atom, thêm 2 trạng thái.

    Ví dụ: a → 2; a|b → 6; (a|b)* → 8; ab|c → 8.

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

      Một dòng: biểu thức chính quy.

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

      |R| ≤ 200.

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

      In một số nguyên: số trạng thái NFA.

    Ví dụ:

    Đầu vào:

    a|b

    Đầu ra:

    6

    Giải thích:

    2 atom (4) + 1 cụm hợp (2) = 6.

    Đang tải editor...