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

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

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

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

EPS - переход epsilon

1, EPS = 2

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

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

6
задан Darkhydro 14 February 2011 в 20:49
поделиться