Cho bảng chữ Σ và hai biểu thức chính quy R1, R2. Kiểm tra chúng có tương đương không, tức L(R1) = L(R2).
Gợi ý: xây DFA đầy đủ cho mỗi biểu thức (kể cả trạng thái chết) rồi duyệt tích hai DFA; nếu tồn tại trạng thái tích mà một bên nhận còn bên kia không thì khác nhau.
Ví dụ: (aa)*|a(aa)* tương đương a* trên Σ={a}.
Dòng 1: Σ. Dòng 2: R1. Dòng 3: R2.
|Σ| ≤ 6, |R1|,|R2| ≤ 200.
In TUONGDUONG hoặc KHAC.
Ví dụ:
Đầu vào:
a
(aa)*|a(aa)*
a*
Đầu ra:
TUONGDUONG
Giải thích:
Đang tải editor...