Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв».
У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог изменить их для эффективного подсчета.
Кажется, что ограниченная природа обычных языков должна сделать их подсчет относительно простым - я почти ожидаю, что формула больше, чем алгоритм. К сожалению, мои поиски до сих пор ничего не дали, поэтому я должен использовать неправильные термины.
Ответы:
Для DFA, в котором начальным состоянием является состояние , количество слов длины которые заканчиваются в состоянии равно , где - матрица передачи DFA (матрица, в которой число в строке и столбце - это количество различных входных символов, которые вызывают переход из состояния в состояние ). Таким образом, вы можете легко подсчитать количество принимаемых слов длиной , даже если умеренно велико, просто вычислив степень матрицы и добавив записи, соответствующие принятым состояниям.k i A k [ 0 , i ] A i j i j k k0 К я AК[ 0 , я ] A я J я J К К
То же самое работает для приема слов длиной не более с немного другой матрицей. Добавьте дополнительную строку и столбец матрицы, с одним в ячейке, находящейся как в строке, так и в столбце, одним в новой строке и столбце исходного состояния и нулем во всех остальных ячейках. Эффект этого изменения в матрице заключается в добавлении еще одного пути к начальному состоянию при каждой степени.К
Это не работает для НФА. Я подозреваю, что лучшее, что нужно сделать, - это просто преобразовать в DFA, а затем применить алгоритм включения матрицы.
источник
Очевидно:
Это восходит к технике, введенной для грамматик Хомским и Шютценбергером (1963); он легко переходит к конечным автоматам.
источник
Я думаю, что это сложная проблема подсчета, см. Эту статью: Подсчет размера регулярных последовательностей заданной длины # P-полон: S. Kannan, Z. Sweedyk и SR Mahaney. Подсчет и случайная генерация строк на обычных языках. В Симпозиуме ACM-SIAM по дискретным алгоритмам (SODA), стр. 551–557, 1995.
источник
источник