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] NFA-epsilon có chấp nhận chuỗi không

    Cho NFA có epsilon N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F)N=(Q,Σ,δ,q0​,F) và chuỗi www. Xác định NNN có chấp nhận www không.

    Mô phỏng: tập trạng thái hiện tại luôn được lấy bao đóng-ε\varepsilonε. Khởi đầu S=ECLOSE({q0})S=\text{ECLOSE}(\{q_0\})S=ECLOSE({q0​}). Với mỗi ký tự aaa: S←ECLOSE(⋃s∈Sδ(s,a))S\leftarrow\text{ECLOSE}\big(\bigcup_{s\in S}\delta(s,a)\big)S←ECLOSE(⋃s∈S​δ(s,a)). Chấp nhận nếu S∩F≠∅S\cap F\neq\varnothingS∩F=∅ sau khi đọc hết www.

    Ví dụ: NFA-ε\varepsilonε cho a∗b∗a^*b^*a∗b∗.

    • Đị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; ký hiệu eps cho bước chuyển epsilon (ε\varepsilonε). Dòng cuối: chuỗi www (có thể rỗng — dòng trống).

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

      1≤Q≤5001 \le Q \le 5001≤Q≤500, 0≤∣w∣≤1040 \le |w| \le 10^40≤∣w∣≤104, 0≤T≤50000 \le T \le 50000≤T≤5000.

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

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

    Ví dụ:

    Đầu vào:

    3
a b
0
1 2
4
0 a 0
0 eps 1
1 b 1
1 eps 2
ab

    Đầu ra:

    YES

    Giải thích:

    NFA-eps cho a*b*. ECLOSE(0)={0,1,2}. Đọc 'a': {0}->ECLOSE={0,1,2}. Đọc 'b': từ 1->1, ECLOSE={1,2}. Giao F={2} -> YES.

    Đang tải editor...