Semplifica l'espressione regolare in Mathematica

Question

Recentemente ho scoperto circa Kleene algebra per la manipolazione e la semplificazione delle espressioni regolari.

Mi chiedo se questo è stato integrato in programmi software computazionali come Mathematica? Sarebbe bello avere uno strumento computazionale per fare unioni e concatenazioni di grandi espressioni e far sì che il computer li semplifichi.

Se non sei a conoscenza di alcun programma con questo algebra integrato, conosci qualche programma che consente di estendere i loro motori con nuove algebre?

Answer 1

Su http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, essa afferma:

Uno dei risultati fondamentali della teoria degli automi finiti è il famoso teorema Kleene, in cui si afferma che una lingua è accettabile da un automa a stati finiti se e solo se può essere rappresentato da un'espressione regolare .

e

La difficoltà principale del trattamento algoritmica dei regolari espressioni è, tuttavia, la loro semplificazione. Sebbene siano note più identità relative alle espressioni regolari, ad esempio le regole dell'algebra di Kleene, non esiste un algoritmo efficace per che risolva il problema di semplificazione delle espressioni regolari.

e

In queste circostanze, l'unico modo è quello di sviluppare sinistra euristiche algoritmi per la semplificazione delle espressioni regolari. Per il pacchetto aut, , questo documento descrive le procedure Maple Rsimplify, Rabsorb e Rexpand.

Mi chiedo se esistono implementazioni open-source di algoritmi Kleene Algebra.