Thuật toán dựng tập con (subset construction) chuyển một NFA (không có ε, nhưng có thể không đơn định trên cùng một kí tự) thành DFA tương đương: mỗi trạng thái DFA là một tập con các trạng thái NFA, trạng thái bắt đầu DFA là {0}, và với mỗi kí tự c, dịch chuyển từ tập S là hợp các dịch chuyển theo c của mọi trạng thái trong S (có thể là tập rỗng — trạng thái "chết"). Chỉ xây dựng các trạng thái có thể đến được từ {0}.
Cho một NFA trên bảng chữ cái gồm σ kí hiệu đầu tiên (a, b, ...), hãy tính: (1) số trạng thái DFA có thể đến được (kể cả trạng thái ứng với tập rỗng nếu nó xuất hiện), và (2) trong số đó, có bao nhiêu trạng thái là chấp nhận (tập con tương ứng giao với tập trạng thái kết thúc của NFA khác rỗng).
Dòng 1: ba số nguyên n m sigma — số trạng thái NFA (đánh số 0,…,n−1, trạng thái 0 là bắt đầu), số dịch chuyển, số kí hiệu trong bảng chữ cái (kí hiệu là σ chữ cái đầu tiên a, b, c, ...).
Dòng 2: số nguyên f rồi f chỉ số trạng thái kết thúc của NFA.
m dòng tiếp theo, mỗi dòng u c v — dịch chuyển từ u đến v theo kí hiệu c (không có ε; có thể có nhiều dòng cùng u c khác nhau về v).
Một dòng hai số nguyên cách nhau khoảng trắng: số trạng thái DFA đến được, và số trạng thái DFA chấp nhận trong số đó.
Ví dụ: NFA 2 trạng thái, kết thúc {1}, dịch chuyển 0 a 0 và 0 a 1 (một kí hiệu a), kết quả là 2 1.
Ví dụ:
Đầu vào:
2 2 1
1 1
0 a 0
0 a 1
Đầu ra:
2 1
Đầu vào:
2 1 1
1 1
0 a 1
Đầu ra:
3 1
Đang tải editor...