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] Chuỗi được chấp nhận ngắn nhất

    Cho DFA M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)M=(Q,Σ,δ,q0​,F). Tìm chuỗi www ngắn nhất được MMM chấp nhận. Nếu nhiều chuỗi cùng độ dài ngắn nhất, in chuỗi nhỏ nhất theo thứ tự từ điển (thứ tự ký tự theo thứ tự tăng của bảng chữ cái).

    Nếu ngôn ngữ rỗng in -1. Chuỗi rỗng biểu diễn bằng một dòng trống.

    Thuật toán: BFS từ q0q_0q0​, mỗi trạng thái duyệt các ký tự theo thứ tự tăng để nghiệm tối tiểu từ điển.

    Ví dụ: DFA chấp nhận chuỗi có số 111 chẵn -> chuỗi ngắn nhất là chuỗi rỗng.

    • Đị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.

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

      1≤Q≤10001 \le Q \le 10001≤Q≤1000, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26.

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

      In chuỗi ngắn nhất (nhỏ nhất từ điển) được chấp nhận; dòng trống nếu là chuỗi rỗng; -1 nếu ngôn ngữ rỗng.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    ab

    Giải thích:

    F={2}. Từ 0: 'a'->1, 'ab'->2 (độ dài 2). Chuỗi ngắn nhất được chấp nhận là 'ab'.

    Đang tải editor...