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] Bổ sung DFA và đếm chuỗi bị từ chối độ dài n

    Cho DFA đầy đủ MMM và số nguyên nnn. DFA bổ sung (complement) M‾\overline{M}M nhận đúng những chuỗi mà MMM từ chối, thu được bằng cách hoán đổi tập trạng thái chấp nhận: F‾=Q∖F\overline{F}=Q\setminus FF=Q∖F.

    Hãy đếm số chuỗi độ dài đúng nnn mà M‾\overline{M}M chấp nhận (tức số chuỗi độ dài nnn bị MMM từ chối).

    Vì MMM đầy đủ, tổng số chuỗi độ dài nnn là ∣Σ∣n|\Sigma|^n∣Σ∣n; kết quả = ∣Σ∣n|\Sigma|^n∣Σ∣n trừ số chuỗi MMM chấp nhận.

    Ví dụ: ∣Σ∣=2|\Sigma|=2∣Σ∣=2, n=2n=2n=2 có 444 chuỗi; nếu MMM nhận 222 thì M‾\overline{M}M nhận 222.

    • Đị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. 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). Dòng cuối: số nguyên nnn.

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

      1≤Q≤2001 \le Q \le 2001≤Q≤200, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26, 0≤n≤10000 \le n \le 10000≤n≤1000. DFA đầy đủ.

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

      In một số nguyên: số chuỗi độ dài nnn được M‾\overline{M}M 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:

    2

    Giải thích:

    M nhận 'số 1 chẵn'; độ dài 2 M nhận '00','11' (2). Bổ sung nhận '01','10' -> 2.

    Đang tải editor...