Cho DFA M=(Q,Σ,δ,q0,F). Một trạng thái s là trạng thái chết (dead/trap) nếu từ s không thể đi tới bất kỳ trạng thái chấp nhận nào.
Hình thức: s chết nếu ∀w∈Σ∗: δ^(s,w)∈/F.
Hãy đếm và liệt kê các trạng thái chết theo thứ tự tăng dần. Thuật toán: BFS ngược từ tập F trên đồ thị chuyển; trạng thái không tới được F là trạng thái chết.
Ví dụ: trạng thái bẫy gom các bước chuyển không hợp lệ chính là trạng thái chết.
Dòng 1: số nguyên Q — số trạng thái (đánh số 0..Q−1).
Dòng 2: các ký tự bảng chữ cái Σ, phân tách bởi dấu cách.
Dòng 3: trạng thái bắt đầu q0.
Dòng 4: số trạng thái chấp nhận F 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×∣Σ∣ dòng, mỗi dòng p a q nghĩa là δ(p,a)=q.
1≤Q≤1000, 1≤∣Σ∣≤26.
Dòng 1: số trạng thái chết. Dòng 2: danh sách các trạng thái chết tăng dần (cách nhau dấu cách); nếu không có in dòng trống.
Ví dụ:
Đầu vào:
3
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 1
2 0 2
2 1 2
Đầu ra:
2
1 2
Giải thích:
Đang tải editor...