Đơn giản hóa biểu thức chính quy trong Mathematica

Question

Gần đây tôi đã tìm ra khoảng Kleene algebra để thao tác và đơn giản hóa các biểu thức chính quy.

Tôi tự hỏi liệu điều này có được xây dựng trong bất kỳ chương trình phần mềm tính toán nào như Mathematica không? Nó sẽ là tuyệt vời để có một công cụ tính toán để làm công đoàn và nối của các biểu thức lớn và có máy tính đơn giản hóa chúng.

Nếu bạn không biết về bất kỳ chương trình nào có đại số này được xây dựng, bạn có biết bất kỳ chương trình nào cho phép mở rộng công cụ của họ bằng đại số mới không?

Answer 1

On http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, nó khẳng định:

Một trong những kết quả cơ bản của lý thuyết automata hữu hạn là lý Kleene nổi tiếng, trong đó nêu rằng một ngôn ngữ được chấp nhận bởi một automaton hữu hạn khi và chỉ khi nó có thể được biểu diễn bằng cụm từ thông dụng .

và

Khó khăn chính của việc điều trị thuật toán thường xuyên biểu thức, tuy nhiên, đơn giản hóa của họ. Mặc dù một số thông tin về số được biết đến liên quan đến cụm từ thông dụng, ví dụ: các quy tắc của đại số Kleene, không tồn tại thuật toán hiệu quả cho việc giải quyết vấn đề đơn giản hóa biểu thức chính quy.

và

Dưới hoàn cảnh, cách duy nhất còn lại là phát triển thuật toán heuristic cho việc đơn giản hóa biểu thức thông thường. Đối với gói aut, bài báo này phác thảo các thủ tục Maple Rsimplify, Rabsorb và Rexpand.

Tôi tự hỏi liệu việc triển khai mã nguồn mở của thuật toán Đại số Kleene có tồn tại hay không.