Мне нужна библиотека, которая будет принимать два регулярных выражения и определить, являются ли они изоморфными (т.е. соответствуют точно одному набору строк или нет) Например, a | b изоморфно [ab]
Как я понимаю, регулярное выражение может быть преобразовано в NFA, который в некоторых случаях может быть эффективно преобразован в DFA. Затем DFA можно преобразовать в минимальный DFA, который, если я его правильно понимаю, уникален, и поэтому эти минимальные DFA можно сравнить для равенства. Я понимаю, что не все регулярные выражения NFA могут быть эффективно преобразованы в DFA (особенно когда они генерировались из Perl Regexps, которые не являются по-настоящему "регулярными" ), и в этом случае в идеале библиотека просто вернет ошибку или какое-то другое указание на то, что преобразование невозможно.
Я вижу тонны статей и научных статей в Интернете об этом (и даже некоторые задания по программированию для классов, предлагающих студентам сделать это), но я не могу найти библиотеку, которая реализует эту функциональность. Я бы предпочел библиотеку Python и/или C/С++, но библиотека на любом языке будет делать. Кто-нибудь знает, есть ли такая библиотека? Если нет, кто-то знает о библиотеке, которая приближается, которую я могу использовать в качестве отправной точки?