Минимизация регулярного выражения

Question

Я довольно новичок в мире программирования.Я пытаюсь создать общее регулярное выражение, которое будет соответствовать только списку приведенных строк, не более того.

Для примера, учитывая приведенный ниже список

List = ['starguide,'snoreguide','snoraguide','smarguides']

Это должно создать регулярное выражение, подобное этому - s(((tar|nor(e|a))(guide))|marguides)

Я реализовал три.Можно было только получить s(marguides|nor(aguide|eguide)|targuide)

Я хочу, чтобы мое регулярное выражение было сокращено (общие суффиксы связаны вместе).Есть ли лучший способ сократить регулярное выражение, которое я получаю от три?

Answer 1

Чтобы получить желаемый результат, попробуйте использовать автоматную минимизацию.

Для вашего простого примера достаточно детерминированного автомата.

Используйте github.com/siddharthasahu/automata-from-regex для построения минимального детерминированногоконечный автомат / автомат из тривиального регулярного выражения (перечисление слов), затем преобразуйте автомат в регулярное выражение (это легко для ациклических автоматов, http://www -igm.univ-mlv.fr / ~ dr / thdr / www.dcc.fc.up.pt / ~ nam / publica / extAbsCIAA05.pdf) см. также https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions

В общем случае недетерминированные автоматы могут привести к более короткому регулярному выражению, но это трудная проблема https://cstheory.stackexchange.com/questions/31630/how-can-one-actually-minimize-a-regular-expression