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

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

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

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

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

1, ЭПС = 2

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

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


java optimization finite-automata
person Darkhydro    schedule 14.02.2011    source источник
comment
Просто для уточнения: эпсилон-замыкание Epsilon-NFA N - это просто NFA без эпсилон-переходов?   -  person tkr    schedule 14.02.2011
comment
@tkr замыкание эпсилон не применяется к NFA. Он применяется к состоянию, которое имеет 1 или более эпсилон-переходов в другое состояние (состояния) и возвращает одно состояние. Он используется, чтобы избавиться от эпсилон-переходов при преобразовании в DFA, потому что DFA не может иметь эпсилон-переходов.   -  person Darkhydro    schedule 14.02.2011
comment
@Darkhydro, вы не можете просто свернуть все эпсилон-достижимые состояния вместе. Рассмотрим s1--a-->s2, s1--b-->s3, s2--eps->s3, s2--c-->s4, начальное состояние s1, принимающее состояние s4. Если вы сворачиваете s2 и s3 в одно состояние, вы принимаете строку bc, которая не принимается исходным NDFA.   -  person Peter Taylor    schedule 14.02.2011
comment
@ Питер, я понимаю твою точку зрения. Я изучаю это.   -  person Darkhydro    schedule 14.02.2011
comment
@Peter на самом деле не примет b. Состояние 1 по-прежнему будет переходить в 3 на входе b, а не в 23. Создание состояния 23 не стирает состояние 3.   -  person Darkhydro    schedule 14.02.2011
comment
Состояние в НКА N=(Q,Sigma,delta,q_0,F) — это просто элемент множества Q. Состояние без дельты не имеет смысла.   -  person tkr    schedule 16.02.2011

Ответы (4)


arrow_upward
3
arrow_downward

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

person Xodarap    schedule 14.02.2011
comment
это оказалось лучшим решением. Очень явно, потому что я могу посмотреть исходный код. Спасибо! - person Darkhydro; 15.02.2011

arrow_upward
4
arrow_downward

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

person Peter Taylor    schedule 14.02.2011
comment
Поиски @Peter - это не совсем то, к чему я стремлюсь. Это скорее условный обход. Однако мой шаблон очень похож на поиск в глубину. - person Darkhydro; 14.02.2011
comment
@Darkhydro, насколько я понимаю, проблема в том, что вы ищете все состояния, достижимые эпсилон из заданного состояния. - person Peter Taylor; 14.02.2011
comment
@Peter, это разумный взгляд на вещи. Однако, если поиск возвращает только одно состояние, мне пришлось бы искать несколько раз, чтобы получить все состояния, что было бы медленнее, чем моя реализация, потому что каждый поиск начинается снова с самого начала. - person Darkhydro; 14.02.2011
comment
@Darkhydro, у меня сложилось впечатление, что вам было бы полезно получить представление о структурах данных и алгоритмах и прочитать о поиске в глубину. У меня на полке стоит книга Introduction to Algorithms Кормена, Лейзерсона и Ривеста. - person Peter Taylor; 14.02.2011
comment
@Peter Может быть, я смотрю на это неправильно. У меня есть собственная литература по алгоритмам, и я буду освежать поиск в глубину. Насколько я понял, поиск вернул только 1 результат. - person Darkhydro; 14.02.2011
comment
Как обычно понимается, он помечает все достижимые вершины. - person Peter Taylor; 14.02.2011
comment
@Darkhydro, что он имеет в виду (по крайней мере, как я это понимаю, и это решение, которое я использую), заключается в том, что вы подходите к проблеме так же, как и к поиску в ширину (только с использованием переходов эпсилон), и просто сохраняете все узлы, к которым вы переходите. Сделай так. В этом случае это будет скорее обход с первым вдохом, а не поиск, но фактический алгоритм практически идентичен. - person cyphar; 04.07.2014

arrow_upward
0
arrow_downward

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

Просмотрите литературу по алгоритмам.

person jmg    schedule 14.02.2011
comment
Я согласен, производительность будет зависеть от структуры данных, которую я использую. Если бы вы могли предложить оптимальную структуру данных плюс алгоритм обхода, это был бы лучший ответ. Моя текущая структура данных - это просто список/дерево. - person Darkhydro; 14.02.2011

arrow_upward
0
arrow_downward

Просто для того, чтобы люди, которые ищут только конкретный фрагмент кода, на который ссылается ответ @Xodarap, не нуждались в загрузке как исходного кода, так и приложения для просмотра кода файла jar, я позволил себе прикрепите указанный фрагмент.

public static State[] getClosure(State state, Automaton automaton) {
    List<State> list = new ArrayList<>();
    list.add(state);
    for (int i = 0; i < list.size(); i++) {
        state = (State) list.get(i);
        Transition transitions[] = automaton.getTransitionsFromState(state);
        for (int k = 0; k < transitions.length; k++) {
            Transition transition = transitions[k];
            LambdaTransitionChecker checker = LambdaCheckerFactory
                    .getLambdaChecker(automaton);
            /** if lambda transition */
            if (checker.isLambdaTransition(transition)) {
                State toState = transition.getToState();
                if (!list.contains(toState)) {
                    list.add(toState);
                }
            }
        }
    }
    return (State[]) list.toArray(new State[0]);
}

Само собой разумеется, что вся заслуга принадлежит @Xodarap и проекту JFLAP.

person blastervla    schedule 01.07.2021