Trong quá trình xây dựng động cơ regex (regex engine), một bước quan trọng của các thuật toán Thompson construction / subset construction là tính bao đóng epsilon (epsilon-closure) của một tập trạng thái trong NFA.
Cho một NFA có n trạng thái đánh số từ 0 đến n−1 và m cạnh chuyển. Mỗi cạnh có dạng (u,v,c): từ trạng thái u có một chuyển sang trạng thái v khi đọc ký hiệu c; riêng khi c là ký tự E (chữ E in hoa) thì đây là chuyển epsilon (không cần đọc ký hiệu nào để thực hiện chuyển này).
Cho tập trạng thái ban đầu S (có thể có 0 phần tử), hãy tính bao đóng epsilon của S: tập tất cả các trạng thái có thể đến được từ S chỉ bằng các chuyển epsilon (một trạng thái luôn thuộc bao đóng epsilon của tập chứa nó, kể cả khi nó không có cạnh epsilon đi ra).
Ví dụ: với n=4, m=4 và các cạnh (0,1,E), (1,2,E), (2,3,a), (0,3,b), S={0}: bao đóng epsilon của S là {0,1,2} (trạng thái 3 không thuộc bao đóng vì cạnh (2,3) đọc ký hiệu a, không phải epsilon; cạnh (0,3,b) cũng vậy).
Dòng 1: hai số nguyên n và m.
m dòng tiếp theo, mỗi dòng gồm ba giá trị u, v, c cách nhau bởi khoảng trắng (0≤u,v<n; c là một ký tự — có thể là chữ cái/chữ số làm ký hiệu, hoặc chữ E biểu diễn epsilon).
Dòng tiếp theo là số nguyên k (0≤k≤n) — số trạng thái trong tập ban đầu S.
Nếu k>0: dòng cuối cùng gồm k số nguyên là các trạng thái của S, cách nhau bởi khoảng trắng. Nếu k=0 thì S=∅ (dòng cuối có thể không xuất hiện hoặc là dòng rỗng).
In ra một dòng gồm các trạng thái thuộc bao đóng epsilon của S, liệt kê theo thứ tự tăng dần, cách nhau bởi đúng một khoảng trắng. Nếu bao đóng rỗng (chỉ xảy ra khi k=0), in ra một dòng rỗng.
Với ví dụ ở trên, kết quả in ra là:
0 1 2
Ví dụ:
Đầu vào:
4 4
0 1 E
1 2 E
2 3 a
0 3 b
1
0
Đầu ra:
0 1 2
Đầu vào:
3 2
0 1 E
1 2 a
0
Đầu ra:
Đang tải editor...