Т.е., я получаю список слов и хочу построить простое регулярное выражение из того, которое соответствует хотя бы всем словам (но может быть и больше).
Я хочу иметь алгоритм для этого. То есть ввод этого алгоритма представляет собой список слов, а вывод - регулярное выражение. Очевидно, будут некоторые ограничения. Как и регулярное выражение всегда будет соответствовать большему количеству слов, если оно должно соответствовать бесконечному количеству слов, и я даю ему только конечное количество слов. Или мне понадобится более компактное представление ввода. Или я также подумываю о предоставлении мне некоторого регулярного выражения в качестве входных данных и списка дополнительных слов, и я хочу получить регулярное выражение, которое соответствует всем им вместе (и, возможно, больше). В любом случае, он должен попытаться создать регулярное выражение, максимально простое.
Какие существуют методы, которые могут это сделать?
Я был совершенно неправильно понят. Я знаю общие принципы регулярных выражений. Я знаю, что это. И в большинстве случаев я могу довольно легко придумать регулярное выражение для некоторого языка от руки. Но я ищу алгоритмы, которые это делают.
Снова сформулировано немного по-другому:
Пусть L - обычный язык. Пусть M_n - конечное подмножество в L с n элементами. Пусть M_n является подмножеством M_ (n + 1).
Я хочу иметь алгоритм LRE, который получает конечный набор слов и выводит регулярное выражение. И я хочу иметь собственность:
lim_n-> бесконечность | diff (LRE (M_n), L) | = 0