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

    solution

    Đề bài: [Trình biên dịch] Rút gọn DFA — số trạng thái tối thiểu

    Trong quá trình xây dựng lexer, một DFA thường được rút gọn (minimize) để có số trạng thái ít nhất có thể mà vẫn nhận đúng cùng một ngôn ngữ — điều này giúp bảng chuyển trạng thái của lexer nhỏ gọn hơn.

    Cho một DFA đầy đủ (mọi trạng thái đều có bước chuyển xác định cho mọi ký tự trong bộ chữ cái Σ\SigmaΣ, không có −1-1−1) với QQQ trạng thái, trạng thái bắt đầu là 000, và tập trạng thái kết thúc cho trước. Hãy tính số trạng thái tối thiểu của DFA tương đương (nhận đúng cùng ngôn ngữ), theo quy trình chuẩn:

    1. Loại bỏ các trạng thái không thể đến được (unreachable) từ trạng thái bắt đầu 000 — các trạng thái này không ảnh hưởng đến ngôn ngữ và bị loại khỏi việc đếm.
    2. Trong số các trạng thái còn lại (reachable), gộp các trạng thái tương đương bằng thuật toán làm mịn phân hoạch (partition refinement — thuật toán Moore): khởi tạo phân hoạch thành 2 lớp (kết thúc / không kết thúc); lặp lại việc tách một lớp thành các lớp con nếu hai trạng thái trong cùng lớp có bước chuyển (theo cùng một ký tự) dẫn đến hai lớp khác nhau, cho đến khi phân hoạch ổn định.

    Kết quả cần tìm là số lớp tương đương thu được ở bước 2 (chính là số trạng thái của DFA tối thiểu).

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

      Dòng 1: hai số nguyên QQQ và kkk (1≤Q≤2001 \le Q \le 2001≤Q≤200, 1≤k≤201 \le k \le 201≤k≤20) — số trạng thái và kích thước bộ chữ cái. Dòng 2: kkk ký hiệu của bộ chữ cái, cách nhau dấu cách. QQQ dòng tiếp theo, dòng thứ iii (ứng trạng thái i−1i-1i−1) gồm kkk số nguyên trong [0,Q−1][0, Q-1][0,Q−1]: bước chuyển của trạng thái i−1i-1i−1 theo từng ký hiệu tương ứng, theo đúng thứ tự đã liệt kê ở dòng 2 (DFA đầy đủ, không có bước chuyển thiếu). Dòng cuối: số nguyên AAA (số trạng thái kết thúc) rồi AAA số nguyên là các trạng thái kết thúc (nếu A=0A=0A=0, chỉ có số 000 trên dòng đó).

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

      In ra một số nguyên duy nhất — số trạng thái của DFA tối thiểu tương đương (chỉ tính trên các trạng thái reachable từ trạng thái 0).

    Ví dụ:

    Đầu vào:

    2 2
0 1
0 1
1 0
1 0

    Đầu ra:

    2

    Đầu vào:

    4 2
a b
1 0
1 2
1 0
1 2
1 3

    Đầu ra:

    1

    Đang tải editor...