solution

Hai biểu thức chính quy được gọi là tương đương nếu chúng biểu diễn cùng một ngôn ngữ (cùng tập hợp xâu được khớp). Đây là bài toán nền tảng để kiểm chứng các phép biến đổi/tối ưu trên động cơ regex — ví dụ kiểm tra xem hai cách viết lại của cùng một mẫu có thực sự sinh ra cùng tập xâu hay không.

Cho hai biểu thức chính quy $p_1, p_2$ (theo đúng văn phạm ở bài "Động cơ regex bằng dựng NFA Thompson"). Gọi $\Sigma$ là hợp các chữ cái thường xuất hiện trong $p_1$ hoặc $p_2$. Hãy xác định $L(p_1) = L(p_2)$ hay không, tức là $p_1$ và $p_2$ có khớp đúng cùng một tập xâu trên $\Sigma^*$ hay không.

Gợi ý cách giải chuẩn: dựng hai DFA $D_1, D_2$ tương ứng cho $p_1, p_2$ trên cùng bảng chữ cái $\Sigma$ (qua NFA Thompson rồi dựng tập con), sau đó duyệt (BFS/DFS) automat tích (product automaton) trên các cặp trạng thái $(u_1, u_2)$, xuất phát từ $(start_1, start_2)$: nếu tồn tại một cặp trạng thái đến được mà đúng một trong hai trạng thái $u_1, u_2$ là trạng thái kết thúc của automat tương ứng (tức cặp này thuộc hiệu đối xứng $L(p_1) \triangle L(p_2)$), thì $p_1$ và $p_2$ không tương đương; nếu duyệt hết mọi cặp đến được mà không gặp trường hợp như vậy thì hai biểu thức tương đương.