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 trạng thái DFA từ NFA-epsilon

    Cho NFA có epsilon N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F)N=(Q,Σ,δ,q0​,F). Khử epsilon và xây dựng tập con để được DFA, đếm số trạng thái tới được của DFA.

    Trạng thái bắt đầu của DFA là ECLOSE({q0})\text{ECLOSE}(\{q_0\})ECLOSE({q0​}). Hàm chuyển: Δ(S,a)=ECLOSE(⋃s∈Sδ(s,a))\Delta(S,a)=\text{ECLOSE}\big(\bigcup_{s\in S}\delta(s,a)\big)Δ(S,a)=ECLOSE(⋃s∈S​δ(s,a)). Đếm số tập con khác nhau (kể cả tập rỗng nếu sinh ra) tới được.

    Ví dụ: NFA-ε\varepsilonε cho a∗a^*a∗ có DFA 111–222 trạng thái tùy cấu trúc.

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

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

      1≤Q≤161 \le Q \le 161≤Q≤16, 1≤∣Σ∣≤51 \le |\Sigma| \le 51≤∣Σ∣≤5, 0≤T≤2000 \le T \le 2000≤T≤200.

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

      In một số nguyên: số trạng thái tới được của DFA tương đương.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    3

    Giải thích:

    NFA-eps cho a*b*. Trạng thái DFA reachable: ECLOSE(0)={0,1,2}, sau 'b' ={1,2}, sau 'b' từ đó vẫn {1,2}; tập rỗng sinh ra khi đọc 'a' từ {1,2}. Tổng 3 trạng thái.

    Đang tải editor...