Я работаю над программой для преобразования недетерминированных конечных автоматов (NFA) в детерминированные конечные автоматы (DFA). Для этого мне нужно вычислить эпсилон-замыкание каждого состояния в NFA, которое имеет эпсилон-переход. Я уже придумал, как это сделать, но всегда предполагаю, что первое, о чем я думаю, обычно наименее эффективный способ что-то сделать.
Вот пример того, как я могу вычислить простое замыкание эпсилона:
Входные строки для функции перехода: формат - startState, symbol = endState
EPS - переход epsilon
1, EPS = 2
Результаты в новом состоянии {12}
Теперь очевидно, что это очень простой пример. Мне нужно было бы вычислить любое количество переходов эпсилон из любого количества состояний. С этой целью мое решение представляет собой рекурсивную функцию, которая вычисляет эпсилон-замыкание в данном состоянии, глядя на состояние, в которое она имеет эпсилон-переход. Если это состояние имеет эпсилон-переходы, тогда функция вызывается рекурсивно в цикле for для такого количества эпсилон-переходов, которое у нее есть. Это выполнит свою работу, но, вероятно, не самый быстрый способ. Итак, мой вопрос таков: каков самый быстрый способ вычислить замыкание эпсилона в Java?