solution

Xây dựng một động cơ regex theo phương pháp kinh điển: dựng NFA theo thuật toán Thompson từ biểu thức chính quy, rồi mô phỏng NFA đó (bằng $\varepsilon$-closure) để kiểm tra khớp mẫu.

Xét văn phạm biểu thức chính quy trên bảng chữ cái gồm các chữ cái tiếng Anh thường, với các phép toán theo thứ tự ưu tiên tăng dần: hợp | (union) có độ ưu tiên thấp nhất, tiếp theo là nối tiếp (concatenation, được viết ngầm định giữa hai thành phần liền nhau, không có ký hiệu riêng), và lặp Kleene * (star) có độ ưu tiên cao nhất; dấu ngoặc đơn ( ) dùng để nhóm và ghi đè thứ tự ưu tiên mặc định. Một nhánh của phép hợp | được phép rỗng, biểu diễn xâu rỗng $\varepsilon$ — ví dụ mẫu a| khớp a hoặc khớp xâu rỗng.

Cho biểu thức chính quy $p$ (đảm bảo hợp lệ theo văn phạm trên) và một xâu $s$ gồm chữ cái thường, hãy xác định $p$ có khớp toàn bộ (full match, từ đầu tới cuối) xâu $s$ hay không.

Ví dụ: $p =$ (a|b)*abb, $s =$ ababababb → khớp, vì $s$ có thể viết thành $(ab)^3 \cdot abb$... tổng quát hơn: $s$ là một dãy tuỳ ý các ký tự $a,b$ và kết thúc bằng abb.