Обобщение строк и оптимизация конечного автомата

Question

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

Пример:

учитывая строки ['fun', 'gun'], я могу построить регулярное выражение 'fun | gun', но более короткое описание регулярного выражения '[fg] un', я sh, чтобы найти это систематически.

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

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

Answer 1

Минимизация регулярного выражения и минимизация конечного автомата - это очень разные проблемы. Действительно, хотя DFA и регулярные выражения одинаково выразительны (они могут описывать одни и те же языки), между размерами представлений нет простой связи. Существуют DFA, для которых требуются регулярные выражения экспоненциального размера в количестве состояний, а также регулярные выражения, экспоненциально увеличивающиеся при преобразовании в DFA (даже при минимизации). Кроме того, минимизация размера регулярного выражения в принципе неразрешима, в отличие от минимизации состояний в DFA. (Существуют «приблизительно минимальные» алгоритмы, но они не изящны.)

В стандартной библиотеке Python нет пакета для выполнения этих задач. Плохие и защищенные от копирования реализации (иногда даже два в одном) изобилуют в Интернете; По некоторым причинам, почти все реализации, кажется, сделаны или студентами, которые все еще изучают любой язык, на котором они пишут, или учеными, которые думают, что их работа слишком драгоценна, чтобы делиться ими с открытым исходным кодом. В любом случае, предыдущая вспышка является примером того, почему SO не поощряет вопросы «найди мне ресурс»: они, как правило, привлекают взвешенные ответы, которые никому не особенно полезны (кроме, возможно, расчесывания зуда респондента).

Если вы собираетесь программировать, алгоритмы на самом деле довольно просты. Конструкция Томпсона для преобразования регулярных выражений в NFA должна составлять не более ста строк Python, а конструкция блока питания для создания DFA еще проще. Если у вас есть NFA-> DFA, вы можете выполнить минимизацию с помощью алгоритма Бжозовского, который тривиален: инвертируйте DFA, производящий NFA, уменьшите его обратно до DFA, а затем разверните и снова уменьшите. Непонятно, почему это работает, но это работает, и это одна строка кода, когда вы написали реверсор DFA, а это, в свою очередь, полдюжины строк.