solution

Cho bảng chữ Σ và biểu thức chính quy R. Tìm độ dài lớn nhất của một chuỗi thuộc L(R):

• Nếu L(R) rỗng, in -1.
• Nếu độ dài không bị chặn (tồn tại chu trình trên đường đi từ đầu tới trạng thái nhận), in VOHAN.
• Ngược lại in độ dài hữu hạn lớn nhất.

Gợi ý: xây DFA, xác định tập trạng thái vừa tới được từ đầu vừa tới được trạng thái nhận; nếu tập đó chứa chu trình → VOHAN; nếu không → đường đi dài nhất trên DAG.

Ví dụ: a* → VOHAN; abb → 3; @ → -1.