Есть ли способ сортировки списка регулярных выражений по специфике?

Question

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

в соответствии с их спецификой / строгостью

/[a-z]+/           // most strict
/[a-z0-9]+/
/[a-z0-9èòà]+/     // less strict
/.*/

, но как насчет

/[a-z]+ABC/
/[a-z0-9]+/

какой из них менее конкретен, чем другой?

Заранее спасибо

Answer 1

Можно приравнять регулярное выражение к набору соответствующих ему строк (называемых «регулярным языком».) Если наше регулярное выражение называется E, давайте назовем его соответствующие строки L(E).

Строгость в том смысле, на который вы ссылаетесь выше, становится отношением подмножества: определите RE A как более строгий, чем RE B, если L(A) является правильным подмножеством L(B).Это устраняет неоднозначности, такие как синонимы для «одного и того же» RE: они одинаковы именно потому, что имеют один и тот же регулярный язык.

Как указывает @yi_H, отношение подмножества к языкам RE (к некоторому общему алфавиту)) формирует частичное упорядочение.Ты говоришь так, будто хочешь полный порядок.Если это так, вы можете оговорить, что приемлемый общий порядок должен включать частичный порядок, представленный отношением подмножества.

У меня нет четкого ответа о том, как построить этот полный порядок, но на ум приходят два подхода..

Первый - использовать лемму прокачки .Оказывается, что для любого RE, если он соответствует достаточно длинной строке, он также должен соответствовать более длинной строке, которая может быть сконструирована из первой, повторяя некоторый подраздел.Вы можете спросить, какова длина самой длинной совпадающей строки, у которой нет таких повторяющихся сегментов, и сделать это своей метрикой.Может быть, это учитывает (встраивает) частичное упорядочение, а может, и нет.

Другой - рассмотреть преобразования графов на конечном автомате RE.Я подозреваю (но у меня нет никаких ссылок), что если RE A является должным образом более строгим, чем RE B, то автомат B будет вычисляться из A путем сложения состояний или некоторого аналогичного упрощениядействие.Вы можете определить свою метрику как число состояний в самом маленьком автомате RE.

Answer 2

Как показывает ваш второй пример, вы не можете иметь полный порядок регулярных выражений, возможен только частичный порядок .

Что еще хуже, существует множество способов написать одно и то же регулярное выражение: [ab]b против (ab|bb), aa* против a+. Так что даже решить, являются ли два регулярных выражения эквивалентными , не простая задача.

Answer 3

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

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