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 số đường đi chấp nhận trong NFA

    Cho NFA không epsilon N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F)N=(Q,Σ,δ,q0​,F) và chuỗi www. Hãy đếm số đường đi khác nhau trong NFA tương ứng với việc đọc www và kết thúc tại một trạng thái chấp nhận.

    Mỗi đường đi là một dãy trạng thái q0=s0,s1,…,s∣w∣q_0=s_0,s_1,\dots,s_{|w|}q0​=s0​,s1​,…,s∣w∣​ với si+1∈δ(si,wi+1)s_{i+1}\in\delta(s_i,w_{i+1})si+1​∈δ(si​,wi+1​) và s∣w∣∈Fs_{|w|}\in Fs∣w∣​∈F. Dùng quy hoạch động dp[s]dp[s]dp[s] = số đường đi đọc tới sss.

    Ví dụ: trong NFA mơ hồ, một chuỗi có thể có nhiều đường đi chấp nhận.

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

      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 q0q_0q0​. 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. Dòng 5: số bước chuyển TTT. Tiếp theo TTT dòng, mỗi dòng p a q nghĩa là q∈δ(p,a)q\in\delta(p,a)q∈δ(p,a) (NFA, có thể nhiều đích cho cùng (p,a)(p,a)(p,a)). Dòng cuối: chuỗi www (có thể rỗng — dòng trống).

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

      1≤Q≤2001 \le Q \le 2001≤Q≤200, 0≤∣w∣≤10000 \le |w| \le 10000≤∣w∣≤1000. Kết quả có thể lớn.

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

      In một số nguyên: số đường đi chấp nhận khi đọc www.

    Ví dụ:

    Đầu vào:

    3
a
0
1 2
4
0 a 1
0 a 2
1 a 2
2 a 2
aa

    Đầu ra:

    2

    Giải thích:

    Đọc 'aa': đường 0->1->2 và 0->2->2. Cả hai kết thúc ở 2 (thuộc F). Số đường đi chấp nhận = 2.

    Đang tải editor...