Cho bảng chữ Σ (sắp thứ tự từ điển theo ký hiệu) và biểu thức chính quy R. Tìm chuỗi thuộc L(R) nhỏ nhất theo tiêu chí: độ dài ngắn hơn trước, cùng độ dài thì so sánh từ điển. Nếu chuỗi rỗng thuộc L(R) thì đó là nhỏ nhất, in #. Nếu L(R) rỗng, in VONGHIEM.
Gợi ý: xây DFA rồi tìm kiếm ưu tiên theo (độ dài, từ điển) trên các trạng thái.
Ví dụ: Σ={a,b}, R=(a|b)*abb → abb; R=b*a → a.
Dòng 1: Σ. Dòng 2: R.
|Σ| ≤ 6, |R| ≤ 200.
In chuỗi nhỏ nhất, hoặc # (chuỗi rỗng), hoặc VONGHIEM.
Ví dụ:
Đầu vào:
ab
(a|b)*abb
Đầu ra:
abb
Giải thích:
Đang tải editor...