Cho một NFA (không có cạnh ε) và một chuỗi w. Mô phỏng NFA bằng cách giữ tập các trạng thái hiện tại: bắt đầu với {s}, mỗi ký tự lấy hợp các đích khả dĩ. Chuỗi được chấp nhận nếu tập cuối cùng giao với tập chấp nhận khác rỗng.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
3 2
4
0 0 0
0 1 0
0 0 1
1 1 2
0
1 2
ab
Output:
ACCEPT
Khối mô tả NFA gồm:
n k.t — số bộ chuyển.t dòng: mỗi dòng u j v nghĩa là từ trạng thái u đọc ký tự thứ j có thể tới v (không đơn định).s.f rồi f số — tập chấp nhận.
Sau khối NFA là một dòng chứa chuỗi w (- cho chuỗi rỗng).1 ≤ n ≤ 500, 1 ≤ k ≤ 26, |w| ≤ 10^4.
In ACCEPT nếu NFA chấp nhận w, ngược lại REJECT.
Ví dụ:
Đầu vào:
3 2
4
0 0 0
0 1 0
0 0 1
1 1 2
0
1 2
ab
Đầu ra:
ACCEPT
Giải thích:
Đang tải editor...