Подсчет слов, принятых обычной грамматикой

26

Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв».

У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог изменить их для эффективного подсчета.

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

Чарльз
источник
Я полагаю, вы имеете в виду «количество принимаемых слов размером » или что-то в этом роде? иначе, каково количество принимающих слов дляΣ nΣ
Суреш Венкат

Ответы:

38

Для DFA, в котором начальным состоянием является состояние , количество слов длины которые заканчиваются в состоянии равно , где - матрица передачи DFA (матрица, в которой число в строке и столбце - это количество различных входных символов, которые вызывают переход из состояния в состояние ). Таким образом, вы можете легко подсчитать количество принимаемых слов длиной , даже если умеренно велико, просто вычислив степень матрицы и добавив записи, соответствующие принятым состояниям.k i A k [ 0 , i ] A i j i j k k0kiAk[0,i]Aijijkk

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

Это не работает для НФА. Я подозреваю, что лучшее, что нужно сделать, - это просто преобразовать в DFA, а затем применить алгоритм включения матрицы.

Дэвид Эппштейн
источник
2
Идеальный ответ: очевиден только после прочтения.
Чарльз
1
Этот подход имеет экспоненциальное время выполнения в худшем случае, если у вас есть входные данные, отличные от DFA. Это не проблема для вас, @Charles? Кажется, вы включаете в свои вопросы регулярные выражения, NFA и грамматику, а также задаете эффективный способ.
Рафаэль
17

A=(Q={q1,,qn},Σ,δ,QF)q1QFQδQ×Σ×Q

Qi(z)qin[zn]Qi=|{w|w|=nw accepted from qi}|

Очевидно:

Qi(z)=[qiQF]+(qi,a,qj)δxQj(z)

Q1[zn]Q1

Это восходит к технике, введенной для грамматик Хомским и Шютценбергером (1963); он легко переходит к конечным автоматам.

εxaΣwΣkxxk

Рафаэль
источник
Я ценю историческую записку!
Чарльз
1
На самом деле, это метод, который работает очень хорошо (и прост, как только вы его получите) во многих обстоятельствах. Например, вы можете делать CFG точно так же.
Рафаэль
1
Понятно, я не понял. В этом случае, если вы хотите прочитать об этом, я рекомендую Kuich (1970), который мне показался более доступным, чем работа C & S. Он также описывает это в своей книге, которую я не помню.
Рафаэль
1
n
1
@joro В случае однозначных грамматик, я думаю, что это правда, да.
Рафаэль
7

Я думаю, что это сложная проблема подсчета, см. Эту статью: Подсчет размера регулярных последовательностей заданной длины # P-полон: S. Kannan, Z. Sweedyk и SR Mahaney. Подсчет и случайная генерация строк на обычных языках. В Симпозиуме ACM-SIAM по дискретным алгоритмам (SODA), стр. 551–557, 1995.

Миклош Иштван
источник
1
Пост выше предполагает, что данная длина в одинарных. Если вместо этого длина в двоичном виде, проблема PSPACE-сложная. Я говорю это, основываясь на доказательстве того, что решение эквивалентности двух регулярных выражений является PSPACE-трудным. В этом сокращении был создан один reg-ex для приема всех строк, а другой для приема всех строк, которые не являются действительными, отклоняя истории вычислений машины PSPACE M на входе w. Использование этого второго регулярного выражения и длины истории вычислений M на w в качестве входных данных для рассматриваемой проблемы делает эту другую проблему также сложной для PSPACE.
Михаил Рудой