Преобразование регулярного выражения в конечный автомат

Вы бы намекнули на алгоритм для преобразования любого регулярного выражения в конечный автомат. Например, алгоритм, анализирующий регулярное выражение и добавляющий состояния в fsm соответственно? Любая ссылка или более глубокая идея?

Я пишу это с Python

Спасибо и всего наилучшего

 octoback11 июл. 2012 г., 14:39
это только для удовольствия. Я написал общий fsm (очень простой), я хотел бы теперь иметь функцию regExpToFSM (), которая будет создавать fsm, соответствующий заданному регулярному выражению.
 Jeff Tratner11 июл. 2012 г., 09:39
это домашнее задание для класса?
 JBernardo11 июл. 2012 г., 08:24
Попробуйте скомпилировать регулярное выражение сre.DEBUG вариант.
 Bruce11 июл. 2012 г., 08:17
это не то, чтоre.compile в основном делает? Вы хотите переписать regex engineyourself?

Ответы на вопрос(1)

Решение Вопроса

Введение в теорию вычислений, В главе 1 приведены подробные алгоритмы преобразования регулярного выражения в детерминированный или недетерминированный конечный автомат (DFA или NFA) в контексте доказательства их эквивалентности (DFA, NFA и регулярное выражение могут совпадать с одинаковыми классами). строк).

Общая идея такова: вы преобразовываете регулярное выражение в NFA, что может быть сделано довольно просто (* это петля,| и диапазоны символов являются точками ветвления). Затем вы конвертируете NFA в (гораздо больший) DFA, который включает создание одного состояния DFA для каждогоset альтернативных государств NFA. DFA имеет не более столько состояний, сколько набор мощности набора состояний NFA (например, NFA с 3 состояниями может быть преобразован в DFA с максимум 2 ^ 3 = 8 состояниями) и может распознавать любую целевую строку без обратного отслеживания , Прочитайте книгу для деталей.

Ваш ответ на вопрос