Существует ли известный метод построения грамматики по конечному набору конечных строк?

Из моего чтения кажется, что большинство грамматик занимается созданием бесконечного числа строк. Что делать, если вы работали наоборот?

Если задано n строк длиной m, должна быть возможность создать грамматику, которая будет генерировать эти строки и только эти строки.

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

Это относится к общей теме «индукции грамматики»; поиск по этой фразе найдет тонны литературы. См., Например, Введение контекстно-свободной грамматики , https://en.wikipedia.org/wiki/Grammar_induction , https://cstheory.stackexchange.com/q/27347/5038 .

Для регулярных языков (а не контекстных), см. Также Regex golf NP-Complete? , Наималейший DFA , что принимает данный строки и отвергает другие данные строки , Существует ли улучшения в алгоритме Даны Энглиной для обучения регулярных множеств , и https://cstheory.stackexchange.com/q/1854/5038 .

Если число строк конечно, например, установите вы всегда можете придумать грамматику без контекста, которая генерирует все эти строки, пусть не является терминалом, тогда правило может быть . Для конечного набора строк вы можете даже создать автомат с конечным состоянием, который принимает только эти строки. Таким образом, случай конечного набора строк действительно тривиален.A A → s 1 | с 2 | , , , с $S=\{s_1,s_2....s_m\}$$A$$A \to s_1|s_2|...s_n$

Есть много способов, поэтому вам нужно наложить дополнительные критерии качества результатов.

1. Список: для каждой строки в языке есть правило . Пусть будет исходным нетерминалом. Выполнено.S → w $w$$S \rightarrow w$$S$
2. Дерево префиксов: для каждого префикса строки в языке есть нетерминал . Для каждой строки в языке, где является символом, есть правило . Для каждой строки в языке есть правило . Пусть будет исходным нетерминалом. Выполнено.X w w 1 x w 2 x X w 1 → x X w 2 w X w → ϵ X $w$$X_w$$w_1xw_2$$x$$X_{w_1} \rightarrow xX_{w_2}$$w$$X_w \rightarrow \epsilon$$X_\epsilon$
3. Суффикс дерево: то же самое, обратное.
4. Применение алгоритма гарантирует получение грамматики минимального размера, например, с минимальным количеством правил. Я не знаю, как это тяжело.

То, что вы спрашиваете, сродни поисковому индексу. Действительно, Конечные Государственные Преобразователи могут быть созданы и использованы для распознавания переданного им текста. Например, Lucene использует этот алгоритм: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698.

Для практического использования, проверьте это сообщение в блоге Эндрю Галлант: Индекс 1 600 000 000 ключей с автоматами и Rust

В этом посте он описывает метод построения FSA с учетом корпуса текста таким образом, чтобы он распознавал все слова. Конечным результатом является построение приблизительно минимального FST из предварительно отсортированных ключей за линейное время и в постоянной памяти.

Реализация доступна в его fstбиблиотеке: https://github.com/BurntSushi/fst

Ответ на вопрос, заданный reinierpost, который также отвечает на оригинальный вопрос:

Мы строим словарный автомат следующим образом:

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

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

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