Tôi cần một thư viện sẽ có hai biểu thức chính quy và xác định xem chúng có đẳng thức hay không (ví dụ: khớp chính xác cùng một chuỗi hoặc không) Ví dụ a | b là isomorphic để [ab]Thư viện để kiểm tra xem hai biểu thức chính quy có bằng nhau/đẳng cấu
Như tôi đã hiểu, biểu thức chính quy có thể được chuyển đổi thành NFA mà trong một số trường hợp có thể được chuyển đổi thành DFA một cách hiệu quả. DFA sau đó có thể được chuyển đổi thành một DFA tối thiểu, nếu tôi hiểu nó một cách chính xác, là duy nhất và do đó, các DFA tối thiểu này có thể được so sánh với sự bình đẳng. Tôi nhận ra rằng không phải tất cả các biểu thức chính quy của NFA đều có thể được chuyển thành DFA (đặc biệt khi chúng được tạo ra từ Perl Regexps không thực sự là "thông thường") trong trường hợp đó thư viện sẽ trả về lỗi hoặc một số dấu hiệu khác không thể.
Tôi thấy hàng tấn bài báo và tài liệu học thuật trực tuyến về việc này (và thậm chí một số bài tập lập trình cho các lớp yêu cầu học sinh làm điều này) nhưng tôi dường như không thể tìm thấy thư viện thực hiện chức năng này. Tôi thích một thư viện Python và/hoặc C/C++, nhưng một thư viện trong bất kỳ ngôn ngữ nào cũng sẽ làm. Có ai biết nếu như một thư viện? Nếu không, có ai biết thư viện gần đến mức tôi có thể sử dụng làm điểm khởi đầu không?
Đây có phải là bài tập về nhà không? :-) –
No. Đó là một phần của dự án nghiên cứu. Nhưng đây không phải là cốt lõi của dự án vì vậy tôi không muốn dành thời gian để cuộn của riêng mình nếu tôi không phải làm vậy. – user1255384
Tôi chỉ đùa thôi. Đây là một câu hỏi rất hay. Vì vậy, +1. –