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] Tính epsilon-closure của một trạng thái

    Cho NFA có epsilon N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F)N=(Q,Σ,δ,q0​,F) và một trạng thái sss. Hãy tính epsilon-closure (bao đóng-ε\varepsilonε) của sss, tức tập tất cả trạng thái tới được từ sss chỉ bằng các bước chuyển ε\varepsilonε (kể cả chính sss).

    Hình thức: ECLOSE(s)={t:s→ε∗t}\text{ECLOSE}(s)=\{t : s\xrightarrow{\varepsilon^*}t\}ECLOSE(s)={t:sε∗​t}.

    Ví dụ: nếu s→εa→εbs\xrightarrow{\varepsilon}a\xrightarrow{\varepsilon}bsε​aε​b thì ECLOSE(s)={s,a,b}\text{ECLOSE}(s)=\{s,a,b\}ECLOSE(s)={s,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: trạng thái sss cần tính bao đóng-ε\varepsilonε.

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

      1≤Q≤10001 \le Q \le 10001≤Q≤1000, 0≤T≤50000 \le T \le 50000≤T≤5000.

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

      In các trạng thái trong epsilon-closure theo thứ tự tăng dần, cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    3
a
0
1 2
2
0 eps 1
1 eps 2
0

    Đầu ra:

    0 1 2

    Giải thích:

    Từ 0: eps->1, eps->2. Bao đóng-eps của 0 là {0,1,2}.

    Đang tải editor...