Какой самый быстрый способ вычислить эпсилон-замыкание?

Question

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

Вот пример того, как я бы вычислил простое закрытие эпсилона:

Входные строки для функции перехода: формат - startState, symbol = endState

EPS - это эпсилон-переход

1, EPS = 2

Результаты в новом состоянии {12}

Теперь, очевидно, это очень простой пример.Мне нужно было бы иметь возможность вычислить любое количество эпсилон-переходов из любого числа состояний.С этой целью мое решение представляет собой рекурсивную функцию, которая вычисляет эпсилон-замыкание для данного состояния, просматривая состояние, в которое он имеет эпсилон-переход.Если это состояние имеет (ы) эпсилон-переход (ы), то функция вызывается рекурсивно в цикле for для стольких эпсилон-переходов, сколько она имеет.Это выполнит работу, но, вероятно, не самый быстрый способ.Итак, мой вопрос заключается в следующем: какой самый быстрый способ вычислить замыкание эпсилона в Java?

Answer 1

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

Answer 2

JFLAP делает это. Вы можете увидеть их источник - в частности, ClosureTaker.java. Это поиск в глубину (именно это предложил Питер Тейлор), и, поскольку JFLAP использует его, я предполагаю, что это почти оптимальное решение.

Answer 3

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