Библиотека для проверки равенства/изоморфности двух регулярных выражений [закрыто]

Closed. Этот вопрос не по теме. В настоящее время ответы не принимаются.

Хотите улучшить этот вопрос? Обновите вопрос, чтобы он соответствовал теме переполнения стека.

Закрыто 4 года назад.

Мне нужна библиотека, которая будет принимать два регулярных выражения и определять, являются ли они изоморфными (т. е. соответствуют точно одному и тому же набору строк или нет). Например, a|b изоморфен [ab]

Насколько я понимаю, регулярное выражение может быть преобразовано в NFA, который в некоторых случаях может быть эффективно преобразован в DFA. Затем DFA можно преобразовать в минимальный DFA, который, если я правильно понимаю, уникален, и поэтому эти минимальные DFA затем можно сравнить на равенство. Я понимаю, что не все NFA регулярных выражений могут быть эффективно преобразованы в DFA (особенно когда они были сгенерированы из регулярных выражений Perl, которые не являются действительно «регулярными»), и в этом случае в идеале библиотека просто вернула бы ошибку или какое-либо другое указание на то, что преобразование невозможно.

Я вижу множество статей и академических статей в Интернете о том, как это сделать (и даже некоторые задания по программированию для классов, которые просят студентов сделать это), но я не могу найти библиотеку, которая реализует эту функциональность.Я бы предпочел библиотеку Python и/или C/C++, но подойдет библиотека на любом языке. Кто-нибудь знает, есть ли такая библиотека? Если нет, знает ли кто-нибудь о близкой библиотеке, которую я могу использовать в качестве отправной точки?

задан Robᵩ 7 March 2012 в 19:35

0 ответов

Другие вопросы по тегам:

c++ python c regex nfa

Библиотека для проверки равенства/изоморфности двух регулярных выражений [закрыто]

0 ответов

Похожие вопросы: