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ích (giao hoặc hợp)

    Cho hai DFA đầy đủ M1,M2M_1,M_2M1​,M2​ trên cùng bảng chữ cái và một phép toán op (AND = giao, OR = hợp). Xây dựng DFA tích nhận L(M1)∩L(M2)L(M_1)\cap L(M_2)L(M1​)∩L(M2​) (nếu AND) hoặc L(M1)∪L(M2)L(M_1)\cup L(M_2)L(M1​)∪L(M2​) (nếu OR), chỉ giữ các trạng thái tới được từ cặp bắt đầu. Hãy đếm số trạng thái tới được đó.

    Trạng thái tích là cặp (p,q)(p,q)(p,q); chuyển (p,q)→a(δ1(p,a),δ2(q,a))(p,q)\xrightarrow{a}(\delta_1(p,a),\delta_2(q,a))(p,q)a​(δ1​(p,a),δ2​(q,a)). Phép toán chỉ ảnh hưởng tập chấp nhận, không ảnh hưởng số trạng thái tới được.

    Ví dụ: tích hai DFA 222 trạng thái có tối đa 444 trạng thái, nhưng số reachable có thể ít hơn.

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

      Dòng đầu tiên: op là AND hoặc OR. Sau đó là Đầu vào gồm hai DFA liên tiếp, mỗi DFA theo định dạng: 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). Hai DFA dùng chung bảng chữ cái (ghi lại trong từng khối).

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

      1≤Qi≤3001 \le Q_i \le 3001≤Qi​≤300, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26.

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

      In một số nguyên: số trạng thái tới được của DFA tích.

    Ví dụ:

    Đầu vào:

    AND
2
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
2
0 1
0
1 1
0 0 1
0 1 0
1 0 1
1 1 1

    Đầu ra:

    4

    Giải thích:

    M1 đếm chẵn/lẻ số 1, M2 nhận chuỗi chứa ít nhất một 0... Tích duyệt các cặp reachable từ (0,0); ở ví dụ này có 4 cặp tới được.

    Đang tải editor...