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ô phỏng NFA bằng tập trạng thái

    Cho ô-tô-mát hữu hạn không đơn định (NFA) không có epsilon N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F)N=(Q,Σ,δ,q0​,F) và chuỗi www. Hãy mô phỏng NFA bằng cách duy trì tập trạng thái hiện tại và cho biết NFA có chấp nhận www không.

    Khởi đầu tập trạng thái là {q0}\{q_0\}{q0​}. Với mỗi ký tự aaa của www, tập mới là ⋃s∈Sδ(s,a)\bigcup_{s\in S}\delta(s,a)⋃s∈S​δ(s,a). NFA chấp nhận nếu tập cuối giao với FFF khác rỗng.

    Ví dụ: NFA nhận diện chuỗi nhị phân kết thúc bằng 1.

    • Đị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, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26, 0≤∣w∣≤1050 \le |w| \le 10^50≤∣w∣≤105, 0≤T≤Q⋅∣Σ∣⋅Q0 \le T \le Q\cdot|\Sigma|\cdot Q0≤T≤Q⋅∣Σ∣⋅Q.

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

      In YES nếu NFA chấp nhận www, ngược lại NO.

    Ví dụ:

    Đầu vào:

    2
0 1
0
1 1
3
0 0 0
0 1 0
0 1 1
01

    Đầu ra:

    YES

    Giải thích:

    NFA nhận chuỗi kết thúc bằng 1. {0}-0->{0}-1->{0,1}. {0,1} giao F={1} -> YES.

    Đang tải editor...