Một bước quan trọng khi cài đặt động cơ regex hiệu năng cao là chuyển một NFA (có thể có ε-chuyển, không đơn định) thành DFA tương đương bằng thuật toán dựng tập con (subset construction), để việc so khớp tại thời điểm chạy chỉ cần O(∣s∣) bước thay vì mô phỏng đồng thời nhiều nhánh.
Cho một NFA ở dạng mô tả chuẩn (trạng thái 0..n−1, các cạnh chuyển gắn nhãn ký tự hoặc ε, một trạng thái đầu, một tập trạng thái kết thúc), hãy thực hiện dựng tập con bắt đầu từ ε-closure của trạng thái đầu. Quy ước: bảng chữ cái của DFA là tập tất cả các ký tự (khác ε) xuất hiện trong các cạnh chuyển của NFA đã cho. Nếu tại một trạng thái DFA (một tập con trạng thái NFA) và một ký tự c của bảng chữ cái, không có trạng thái NFA nào trong tập đó có cạnh chuyển nhãn c, hãy chuyển sang một trạng thái chết (trap) duy nhất, ứng với tập rỗng; trạng thái chết này chỉ được tính vào kết quả nếu nó thực sự được tạo ra (tức có ít nhất một chuyển tới nó) trong quá trình duyệt các trạng thái đến được (reachable) từ trạng thái đầu của DFA. Một trạng thái DFA được gọi là trạng thái kết thúc nếu tập con trạng thái NFA tương ứng chứa ít nhất một trạng thái kết thúc của NFA.
Hãy tính: (a) tổng số trạng thái của DFA thu được (chỉ tính các trạng thái đến được), và (b) trong số đó có bao nhiêu trạng thái là trạng thái kết thúc.
u v c với c là một chữ cái thường hoặc từ khoá EPS.In ra hai số nguyên trên một dòng, cách nhau một dấu cách: tổng số trạng thái DFA (đến được), và số trạng thái kết thúc trong số đó.
Ví dụ:
Đầu vào:
14 16 1
6
13
0 1 a
2 3 b
4 0 EPS
4 2 EPS
1 5 EPS
3 5 EPS
6 4 EPS
5 7 EPS
5 4 EPS
6 7 EPS
8 9 a
7 8 EPS
10 11 b
9 10 EPS
12 13 b
11 12 EPS
Đầu ra:
5 1
Đầu vào:
10 12 1
0
9
0 1 a
2 3 b
4 5 c
6 2 EPS
6 4 EPS
3 7 EPS
5 7 EPS
8 6 EPS
7 9 EPS
7 6 EPS
8 9 EPS
1 8 EPS
Đầu ra:
5 3
Đang tải editor...