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 chuỗi được chấp nhận có độ dài tối đa n

    Cho DFA M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)M=(Q,Σ,δ,q0​,F) và số nguyên nnn. Đếm số chuỗi www với 0≤∣w∣≤n0\le|w|\le n0≤∣w∣≤n mà MMM chấp nhận.

    Hình thức: tính ∑k=0n∣{w∈Σk:δ^(q0,w)∈F}∣\sum_{k=0}^{n}\big|\{w\in\Sigma^k:\hat\delta(q_0,w)\in F\}\big|∑k=0n​​{w∈Σk:δ^(q0​,w)∈F}​.

    Dùng quy hoạch động theo độ dài và cộng dồn số chuỗi chấp nhận tại mỗi độ dài.

    Ví dụ: DFA chấp nhận số 111 chẵn, n=2n=2n=2: chuỗi rỗng, 00, 11 -> tổng 333.

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

      Dòng 1: số nguyên QQQ — số trạng thái (đánh số 0..Q−10..Q-10..Q−1). Dòng 2: các ký tự bảng chữ cái Σ\SigmaΣ, phân tách bởi dấu cách. Dòng 3: trạng thái bắt đầu q0q_0q0​. Dòng 4: số trạng thái chấp nhận FFF rồi danh sách các trạng thái chấp nhận (cùng dòng, cách nhau dấu cách). Tiếp theo Q×∣Σ∣Q\times|\Sigma|Q×∣Σ∣ dòng, mỗi dòng p a q nghĩa là δ(p,a)=q\delta(p,a)=qδ(p,a)=q. Dòng cuối: số nguyên nnn.

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

      1≤Q≤1001 \le Q \le 1001≤Q≤100, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26, 0≤n≤10000 \le n \le 10000≤n≤1000.

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

      In một số nguyên: tổng số chuỗi độ dài từ 000 tới nnn được chấp nhận.

    Ví dụ:

    Đầu vào:

    2
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
2

    Đầu ra:

    4

    Giải thích:

    Độ dài 0: '' (1). Độ dài 1: 0. Độ dài 2: '00','11' (2). Tổng = 3.

    Đang tải editor...