Cho bảng chữ Σ và biểu thức chính quy R (có thể chứa @ = tập rỗng). Hãy tìm độ dài nhỏ nhất của một chuỗi thuộc L(R). Nếu L(R) rỗng, in -1.
Gợi ý: chuyển sang DFA (xây tập con) rồi BFS từ trạng thái đầu tới trạng thái nhận.
Ví dụ: (a|b)*abb → 3; a* → 0 (chuỗi rỗng); a@ → -1.
Dòng 1: Σ. Dòng 2: R.
|Σ| ≤ 10, |R| ≤ 200.
In độ dài ngắn nhất, hoặc -1 nếu ngôn ngữ rỗng.
Ví dụ:
Đầu vào:
ab
(a|b)*abb
Đầu ra:
3
Giải thích:
Đang tải editor...