Một động cơ regex kiểu NFA thực thi bằng cách duy trì một tập trạng thái tích cực (active set) và cập nhật tập này theo từng kí tự đọc vào, xen giữa là bước đóng ε (epsilon-closure). Cho một NFA với n trạng thái đánh số 0,…,n−1, trạng thái bắt đầu là 0, một tập trạng thái kết thúc, và các dịch chuyển (có thể có ε, kí hiệu #, và có thể không đơn định — nhiều dịch chuyển cùng kí tự từ một trạng thái).
Với mỗi xâu truy vấn, hãy mô phỏng đúng quy trình: bắt đầu từ đóng ε của {0}; với mỗi kí tự c của xâu, tính tập kế tiếp bằng dịch chuyển theo c từ mọi trạng thái đang tích cực rồi lấy đóng ε của tập đó. Sau khi đọc hết xâu, in ACCEPT k nếu tập tích cực cuối cùng giao với tập trạng thái kết thúc khác rỗng, ngược lại in REJECT k, trong đó k là số phần tử của tập tích cực cuối cùng (có thể bằng 0).
Dòng 1: ba số nguyên n m k — số trạng thái, số dịch chuyển, số truy vấn.
Dòng 2: số nguyên f rồi f chỉ số trạng thái kết thúc.
m dòng tiếp theo, mỗi dòng u sym v — dịch chuyển từ u đến v theo kí hiệu sym (một chữ cái thường, hoặc # cho ε).
k dòng tiếp theo, mỗi dòng một xâu truy vấn gồm chữ cái thường (xâu rỗng được biểu diễn bằng kí tự @).
k dòng, mỗi dòng ACCEPT k hoặc REJECT k như mô tả ở trên.
Ví dụ: với NFA 3 trạng thái, kết thúc {2}, dịch chuyển 0 a 1 và 1 # 2, xâu a cho kết quả ACCEPT 2 (tập cuối {1,2}).
Ví dụ:
Đầu vào:
1 0 1
1 0
@
Đầu ra:
ACCEPT 1
Đầu vào:
3 2 2
1 2
0 a 1
1 # 2
a
@
Đầu ra:
ACCEPT 2
REJECT 1
Đang tải editor...