Алгоритм регулярных выражений - комбинаций на или

Question

Я разрабатываю приложение C++ для первого синтаксического анализа строк регулярных выражений, а затем выполняю некоторые вычисления с ним. Существуют ли какие-либо существующие алгоритмы, которые могут выводить число N строк длины L, которое может быть распознано данным регулярным выражением, например (a|ab)* | (aa|bb)*? Или есть математическая формула, которую я могу использовать, например, с факториалами? Я просто хочу получить число N строк, которые могут быть распознаны такими флагами регулярных выражений для заданного числа L. Пример для (a|ab)* того, сколько строк длины 5 (L) может быть распознано регулярным выражением. Я думаю, что ответ будет 5. Но для больших чисел L мне было интересно, есть ли какие-либо алгоритмы или математические выражения, которые могут его вычислить.

Answer 1

Вот эффективный алгоритм, основанный на экспоненциальности матрицы, который вы можете использовать для вычисления этих чисел.

Я собираюсь дать описание высокого уровня, а не код.

1. Во-первых, вы хотите использовать хорошо известную эквивалентность из основ информатики, что (простой) регулярное выражение эквивалентно конечного автомата.

   (Напомним, что конечный автомат, по существу, является блок-схемой последовательности операций, в которой с каждого узла имеется меченое ребро для каждой буквы вашего алфавита на каком-то конкретном другом узле (или, возможно, на его петле). Кроме того, некоторое подмножество состояний называется «Accept Set», а некоторым конкретным состоянием в блок-схеме является начальное состояние. Говорят, что строка индуцирует путь в конечном конечном автомате, начиная с начала и после помеченного ребра подряд. Машина accepts строка, если конечное состояние находится в наборе принятия, и rejects строка в противном случае. Классическая конструкция показывает, что из любого регулярного выражения мы можем построить конечную машину с аналогичным размером и из любого конечного state, мы можем построить регулярное выражение с аналогичным размером. Любой язык (sub множество всех конечных строк), которое соответствует регулярному выражению, называется «регулярным», а язык является регулярным тогда и только тогда, когда он соответствует машине конечного состояния.)

   Например, если у меня есть алфавит {a,b,c} и регулярное выражение (a|b)*, оно соответствует машине с двумя состояниями. Состояние начала имеет петлю, обозначенную a, петлю, помеченную b, и стрелку, обозначенную c, во второе состояние. Второе состояние имеет три петли для себя, поэтому вы попадаете в ловушку, если вы идете туда. Набор accept содержит только начальное состояние.

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

2. Учитывая конечный конечный автомат, я хочу построить соответствующую стохастическую матрицу. В этой матрице мы имеем строку для каждого состояния и столбец для каждого состояния, и каждая запись является вероятностью. Вероятность p_{i,j} при входе (i,j) равна вероятности того, что если я нахожусь в состоянии i, и я прочитал случайное письмо, я перехожу в состояние j дальше. Таким образом, для примера я дал, матрица

   [2/3 1/3]
   [0 1]

3. Если вы хотите знать о строках длины k, а затем с помощью матрицы возведения в степень, вычислить матрица M^k, где M является матрицей перехода вероятности выше.

4. И наконец, если q является начальным состоянием, добавьте все записи M^k_{q, s} для каждого состояния s в принимающем наборе. Сумма этих вероятностей точно равна вероятности того, что регулярное выражение принимает случайную строку длиной k. Таким образом, вы можете получить количество таких строк путем умножения на N^k, где N - это количество букв в вашем алфавите.

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

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

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

Примечание: Если вы действительно хотите реализовать его, я думаю, что вы не должны использовать числа с плавающей запятой, матрица M должна быть фактически матрицей целых чисел. В основном вы умножаете его на N, где N - количество букв в вашем алфавите. И вы пропустите умножение суммы на N^k позже. Я думаю, что легче понять, используя вероятности, но в этой версии M^k_{i,j} будет просто считать number of paths from i to j of length k.

Примечание: Как указано в комментариях, этот алгоритм является многочленом в количестве бит k для любого фиксированного регулярного выражения, поэтому он хорош даже для больших k. Это экспоненциально в худшем случае, хотя в размерном регулярном выражении - для обработки больших и сложных регулярных выражений вы должны использовать некоторую минимизацию DFA, я думаю, если вы хотите использовать этот метод. Для простых регулярных выражений, показанных в вопросе, я думаю, что все должно быть хорошо.